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

Question

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

Сначала у меня есть очень простой вопрос: например, у меня есть такое выражение:* 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).У настоящего парсера их будет десятки.С сотнями.Умело выстраивая их, вы заставляете некоторые вещи сопоставляться с другими.