Нужно ли дополнять грамматики LL (1) посредством перевода при условных или не условных переходах? - PullRequest
Новая
       26

Нужно ли дополнять грамматики LL (1) посредством перевода при условных или не условных переходах?

0 голосов
/ 02 августа 2020

учитывать грамматику ниже 

S -> for id:= E to E by E do S end 
S -> other
E -> num

Предположим, что грамматика выше LL(1), а также SLR(1).

в снизу вверх синтаксический анализатор как Проф. Альфред Вхо в книге принципов, методов и инструментов компиляторов утверждает, что мы действительно дополняем грамматику дополнительными производственными правилами (M -> e) в однопроходном переводе для перевода условного а не условные переходы, например 

S -> for id:= E M to E by E do S M end M
S -> other
E -> num
M -> e {Semantic Action()}

Как видите, мы дополнили грамматику дополнительными производственными правилами (M), поэтому мы знаем trueList и falseList прыжки.

Итак, вот моя основная забота и вопрос: нужно ли нам расширять грамматики Top-Bottom, такие как LL (1), чтобы переводить условные, а не условные переходы, такие как SLR (1)?

1 Ответ

1 голос
/ 03 августа 2020

Авторы этого учебника специально говорят об однопроходном переводе, как вы отметили в своем вопросе. Добавление маркеров нетерминалов - это обычная техника, используемая в грамматиках LR для выполнения действий в середине обработки правой части; Заявление for, которое вы цитируете (или написали), является примером этой техники. (Обратите внимание, однако, что последний M в правой части не нужен; он может быть просто частью действия сокращения для самого оператора for.)

Это вовсе не требование восходящего синтаксического анализа. Лучше было бы описать это как требование однопроходного перевода. Когда писалась книга «Дракон», ограниченная вычислительная мощность компьютеров вынуждала разработчиков компиляторов применять стратегии, позволяющие сократить количество проходов компилятора, но в наши дни такая техника не нужна и обычно нежелательна. Проще, быстрее и универсальнее просто построить абстрактное синтаксическое дерево (AST) во время синтаксического анализа и выполнять все семантичные c анализы, включая генерацию кода, как переходы AST после синтаксического анализа.

Если вы создаете AST, вам больше не нужно играть в алгоритм синтаксического анализа, чтобы выполнять действия в правильной последовательности. Вместо этого вы можете перемещаться по дереву в любом порядке (или порядке), который кажется удобным для конкретного анализа, который вы проводите.

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

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

...