Программа-интерпретатор для учебного языка SPL, страница 2

 — стартовый (главный) нетерминальный символ.

int x, y, z;

DVARB®intl iden (‘,’ iden) *’;’

PROG®(DVARB | DCONST | DFUNC) *eof

Строчные — терминальные, заглавные — нетерминальные.

Работа с цепочками

Предположим, есть две цепочки  и , . И есть правило, что  ( можно заменить на ):

.

Тогда, заменив на , можно из цепочки  получить  (за один шаг). Говорят, что цепочка  является непосредственно выводимой из цепочки :

.

Цепочка  — просто выводимая из цепочки  в двух (2) случаях:

1. ;
2.  последовательность: .

Язык , определяемый грамматикой , — множество цепочек терминальных символов, полученных из стартового нетерминального символа путем применения правил преобразования, перечисленных в множестве  при описании грамматики:

.

Пример:    

                    

                    

                    

Расширенные грамматики

, где ,

                      — нетерминальный символ,

                      — соответствующее ему регулярное выражение .

Самое первое регулярное выражение должно быть для главного стартового нетерминала.

Задача анализа

Дана грамматика. Дано конкретное слово (цепочка символов). Необходимо определить, принадлежит ли это слово к формальному языку, описываемому данной грамматикой. В этом случае реализуется алгоритм LA(1)-анализ (лексический анализ — по одному символу прочитываются слева направо, и осуществляется анализ).

Пусть:     

                 

                 

Цепочка 

Относится ли эта цепочка к данному языку, описываемому данной грамматикой?

Реализуется одна из двух стратегий:

1. сверху вниз — заключается в том, что после прочтения символа начинается анализ со стартового главного нетерминала, и путем выбора правил вывода пытаются получить выводимую цепочку;
2. снизу вверх — прочитываются символы слева направо, и пытаются получить путем выбора правила вывода главный нетерминальный символ.

Пример: (сверху вниз)

                           

                                   

                       

                                   

                       

                                   

                    

                                   

                    

                                   

           

Тогда: цепочка выводится из главного нетерминала.

Синтаксические диаграммы

Синтаксическая диаграмма представляет собой ориентированный граф с двумя вершинами — входной и выходной.®

Каждому нетерминальному символу соответствует регулярное выражение, по которому строится синтаксическая диаграмма: сколько нетерминальных символов, столько и синтаксических диаграмм.

В соответствии с каждой синтаксической диаграммой будет составляться функция для вывода и анализа цепочек, выводимых из этого нетерминального символа (для проверки правильности написания цепочки).

Дуги синтаксической диаграммы могут помечаться или терминальными или нетерминальными символами.

Условились:       терминальные символы обводить в кружочек:

                              а нетерминальные — в квадрат:

                              Регулярное выражение :

Условия применения LA(1)-анализа

1. В синтаксической диаграмме не должно быть непомеченных дуг;
2. в местах разветвления каждая ветвь должна начинаться с разных терминальных символов.

Правила прохождения дуг синтаксической диаграммы

1. Если встретилась дуга, помеченная терминальным символом, то необходимо в анализируемой цепочке распознать этот символ (что именно этот символ, которым помечена дуга)

      и сдвинуться на следующий символ вправо в этой цепочке. Если символ не совпал, то анализ прекращается.