Грамматическая помощь (Теория автоматов)?

Question

Привет, ребята, у меня есть вопрос, простой вопрос с Automaton, я не уверен, является ли это правильным местом или нет psoting такого рода вопроса. На самом деле, в этом году у меня есть курс по компиляции, и если кто-нибудь знает какой-нибудь хороший ресурс, было бы хорошо опубликовать здесь.

Сначала у меня есть очень простой вопрос: например, у меня есть выражение вроде: 2+3*5, как написать грамматику для этого выражения? Я имею в виду один неоднозначный и один не двусмысленный пример Спасибо

Answer 1

Вы не можете "написать грамматику для выражения [an]". Грамматика - это правила производства. Простой пример:

S -> (S)
S -> SS
S -> [empty]

Вы видите, что делает эта грамматика?

По сути, это позволяет генерировать строки типа "", "()", "((()())())". Заметьте, я сказал "сгенерировать" - по логике вы начинаете с одного "S" и начинаете с него, заменяя каждый S на "производство" справа. Но ключ в том, что любая строка, которую вы генерируете этим методом, является "грамматически правильной" в формальном смысле.

Синтаксический анализ является противоположностью этому - превращение строки в соответствующий порядок производств. Грамматика неоднозначна, если это можно сделать несколькими способами.

Когда вы пишете компилятор, сначала вам нужно "лексировать" ввод. 2+3*5 должно быть заключено в нечто вроде NUM ADD NUM TIMES NUM (каждый из них является токеном). Затем вы анализируете токены на основе грамматики, чтобы создать "синтаксическое дерево", возможно, что-то вроде:

  _ + _
2        *
      3/   \5

Вам нужно будет написать правила для производства так, чтобы действительные строки были единственными вещами, которые могут быть сгенерированы. Это немного сложно и немного искусно, поэтому я не могу помочь без более подробной информации.

Приоритет обрабатывается различными нетерминалами (например, S и T). У настоящего парсера их будет десятки. С сотнями. Умело выстраивая их, вы заставляете определенные вещи соответствовать другим.