Вопросы для самопроверки. 1) E:= E+T E =>T =>T*F =>F*F =>i*F =>i*(E) =>i*(E+T) =>i*(T+T) =>

4 6 4 6

2 3 5 1 4 6 2

2 3 4 6 5 1 2

1) E:= E+T E =>T =>T*F =>F*F =>i*F =>i*(E) =>i*(E+T) =>i*(T+T) =>

2) E:=T 4 6 4 6

3) T:=T*F =>i*(F+T) =>i*(i+T) =>i*(i+F) =>i*(i+i).

4) T:=F;

5) F:=(E);

6) F:=i.

Левый разбор: 2 3 4 6 5 1 2 4 6 4 6.

E =>T =>T*F =>T*(E) =>T*(E+T) =>T*(E+F) =>T*(E+i) =>T*(T+i) =>

=>T*(F+i) =>T*(i+i) =>F*(i+i) =>i*(i+i).

Правый разбор: 6 4 6 4 2 6 4 1 5 3 2.

+

+

Пусть имеем G(N, S, P, S) - грамматику и занумерованные правила (см. выше).

Будем писать a_i Þ b_L, если это левый вывод и a_i Þ b_R, если правый.

1. С чем связана способность МП – автомата проводить нисходящий разбор?

2. С чем связана способность МП – автомата проводить восходящий разбор?

3. Как можно сформулировать проблему разбора входной цепочки моделированием МП – автомата?

Синтаксический анализ «сверху вниз»

Любой контекстно свободный язык может быть принят некоторым недетерминированным магазинным автоматом. Из не­детерминированности указанного автомата следует, что построенный на его основе синтаксический анализатор контекстно свобод­ного языка может осуществлять возврат к предыдущему состоянию в про­цессе функционирования. Сам алгоритм синтаксического разбора опреде­ляет вполне однозначный процесс, поэтому, при возникновении необходи­мости выбора одной из возможных логических ветвей, алгоритм выбирает и в дальнейшем следует всегда единственной из возможных логических ветвей. Это означает, что, обнаружив ошибку выбора, необходимо вернуть­ся к моменту осуществления выбора, вновь осуществить выбор и выпол­нить другое перемещение. Однако если на порождающую язык граммати­ку были наложены определенные ограничения, а автомат эффективно ис­пользует свой стек, то становится корректным применение ряда хорошо изученных и отработанных приемов, позволяющих построить эффективный синтаксический анализатор для такого языка. На практике все реальные проекты языков программирования, безусловно, содержат все необходи­мые ограничения, поскольку они получат практическую ценность лишь в том случае, если будут поддержаны достаточно эффективными компиля­торами.

При решении задачи синтаксического разбора строки вида х= =а1,а2…аnЄL(G)используют, как правило, один из двух основных методов. Первый из них заключается в построении дерева вывода, корень которого помечен символом S, а листьями являются узлы, помеченные символами а1,а2…аn.

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