Привет, ребята, у меня есть вопрос, простой вопрос с Automaton, я не уверен, правильно ли это место, чтобы задать такой вопрос. На самом деле в этом году у меня есть курс Compiler Construction, и если кто-нибудь знает какой-нибудь хороший ресурс, было бы неплохо опубликовать его здесь.
Сначала у меня очень простой вопрос: например, у меня есть выражение вроде: 2+3*5 , как написать грамматику для этого выражения? Я имею в виду один неоднозначный и один недвусмысленный пример. Спасибо.
Вы не можете «написать грамматику для выражения». Грамматики — это правила производства. Простой пример:
S -> (S)
S -> SS
S -> [empty]
Вы видите, что делает эта грамматика?
По сути, это позволяет вам генерировать такие строки, как "", "()", "((()())())". Обратите внимание, я сказал «сгенерировать» — логически вы начинаете с одной «S» и работаете дальше, заменяя каждую S некоторым «производством» справа. Но суть в том, что любая строка, сгенерированная этим методом, является «грамматически правильной» в формальном смысле.
Синтаксический анализ является обратным: преобразование строки в соответствующий порядок производства. Грамматика неоднозначна, если это можно сделать более чем одним способом.
Когда вы пишете компилятор, сначала вам нужно «лексировать» ввод. 2+3*5 следует преобразовать в что-то вроде NUM ADD NUM TIMES NUM (каждый из них является токеном). Затем вы анализируете токены на основе грамматики, чтобы построить «синтаксическое дерево», возможно, что-то вроде:
_ + _
2 *
3/ \5
Вам нужно будет написать правила для производства, чтобы допустимые строки были единственными вещами, которые могут быть сгенерированы. Это немного сложно, и немного искусства, так что я не могу помочь без более подробной информации.
Приоритет обрабатывается разными нетерминалами (например, S и T). В реальном парсере их будет несколько десятков. C имеет сотни. Умело располагая их, вы заставляете одни вещи сопоставляться раньше других.
