Учитывая парсер рекурсивного спуска, как мне изменить его для синтаксического анализа?

Question

Я только что закончил кодировать синтаксический анализатор рекурсивного спуска для C минус, который просто печатает «ПРИНЯТЬ», если входной текстовый файл может быть проанализирован, или «ОТКАЗ», если нет.У меня есть функция для каждого правила в грамматике, которая просто возвращает истину или ложь.Вот некоторые из проверок, которые должны быть реализованы в синтаксическом анализе:

По сути, мой вопрос: каков разумный способ сделать это?

У меня сейчас вообще нет таблицы символов, но я слышал, как одноклассники могут просто поставить определенные проверки в самих функциях.Например, чтобы не допустить использование числа с плавающей точкой в ​​качестве индекса массива, просто найдите в моем коде функцию, содержащую скобки, и поставьте там некоторую «проверку», чтобы вернуть ошибку, если число с плавающей точкой находится между двумя скобками.

Answer 1

Ваш список проверок не является "синтаксическим" анализом в смысле грамматических проверок.

Это проверки "синтаксиса", если вы интерпретируете только полностью допустимые программы в качестве экземпляров языка.

Большинствосообщества компиляторов назвали бы эту «семантическую» (валидную) проверку.

Обычно такие проверки касаются того, применяются ли операторы к операндам согласно правилам языка (например, «operator [] не может использоваться, кроме как в массиве»).types ").

Для этого вам необходимо знать для каждого оператора (например," [] "), какой тип операнда.Для этого люди обычно создают таблицы символов, которые сопоставляют идентификаторы с типом идентификатора, и сопоставляют области исходного кода с наборами идентификаторов, которые действительны в этих областях («области»).С помощью этой информации вы можете проверить, что оператор, примененный к символу, имеет смысл.

Теперь возникает сложность: некоторые операторы применяются к выражению s, например, к другим композициям операторов, например:foo(x)[17] что я имею в виду "foo - это функция, которая вызывается и возвращает массив. Так что теперь вам нужно ассоциировать информацию о типе с каждым выражением.

Самый простой способ - связать информацию о типе скаждый узел в дереве. Вам нужно будет прочитать о таблицах символов, о том, как создать одну из них, выполняя обход дерева, а затем о том, как обходить дерево, обозначая каждый узел типом (идентификаторы просты: тип - это то, чтоТаблица symobl сообщает, что тип идентификатора:) Обычно вы можете выполнить обход дерева снизу вверх, сначала пометив конечные узлы, а затем проверить правильность узлов оператора над ними и вычислить тип узла оператора после прохождения проверки валидности,и продолжаем этот процесс для маркировки узлов дерева, когда ваш анализатор поднимается по дереву.

[Дляна некоторых языках сканирование снизу вверх не работает;Вы итеративно передаете информацию вверх и вниз.Ада довольно известна этим].

Формальная характеристика этого процесса называется «оценка атрибута».См. https://en.wikipedia.org/wiki/Attribute_grammar. Вам не нужно быть таким «формальным» для реализации идей, вы можете сделать случай «снизу вверх» вручную.

Это умный способ.Возможны и другие подходы, но их трудно представить и, вероятно, трудно заставить работать «правильно».