Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология Образование Политология Производство Психология Стандартизация Технологии |
Cинтаксический анализ для LL(1)-грамматики
Алгоритм синтаксического анализа на основе LL(K)-грамматики относится к классу алгоритмов нисходящего разбора. Строкам управляющей таблицы М для грамматики G(V,T,P,S) /1/ ставятся в соответствие элементы множества {VUTU$} ($-маркер дна стека), столбцам - элементы множества {T U "lambda"}("lambda" - пустая строка). Перед началом работы алгоритма в рабочий стек заносятся символы $ и S. Возможные значения элементов таблицы и их интерпретация алгоритмом разбора приведены в таблице 1.
аблица 1.
Для построения управляющей таблицы М по заданной LL(1)-грамматике G(V,T,P,S) можно воспользоваться следующим алгоритмом /1/. 1.Усли <A>::=r-правило номер i заданной грамматики,то M(<A>,a)=i для всех a (кроме "lambda"),являющихся терминальными префиксами цепочек, выводимых из r.Если таким префиксом может быть "lambda",то М(<A>,b)=i для всех b,являющихся терминальными символами,которые могут встречаться непосредственно справа от <A>. 2.M(a,a)="сдвиг" для всех a,принадлежащих Т. 3.M($,"lambda")="допуск". 4.Оставшиеся незаполненными элементы таблицы М получают значение "ошибка".
Пример. Зададим грамматику G(V,T,P,S) следующим набором правил (полагая, что терминальные символы в правых частях правил представлены соответствующими кодами лексемы): 1) <S> ::= <E> 2) <E> ::= <T> + <E> 3) <E> ::= <T> 4) <T> ::= <F> * <T> 5) <T> ::= <F> 6) <F> ::= i Грамматика G(V,T,P,S) не обладает свойством LL(1),поскольку обе правые части для нетерминала <E> (правила 2 и 3) порождают цепочки,начинающиеся одним и тем же терминалом i.То же можно сказать и о правилах для терминала <T>. Преобразуем грамматику G(V,T,P,S) к грамматике G1(V1,T,P1,S),обладающей свойством LL(1). Правила последней примут вид: 1) <S>::=<E> 2) <E>::=<T><X> 3) <X>::=+<E> 4) <T>::=<F><Y> 5) <Y>::=*<T> 6) <F>::=i 7) <X>::="iambda" 8) <Y>::="lambda" В соответствии с приведенным алгоритмом теперь можно построить управляющую таблицу для LL(1)-анализатора:
Незаполненные элементы таблицы имеют значение "ошибка". Проанализируем входную цепочку i*i с помощью алгоритма LL(1)-анализатора. При этом, для облегчения формирования выходного стека, при записи символа в рабочий стек будем снабжать его указателем на символ, являющийся его предком в синтаксическом дереве разбора. Процесс анализа проиллюстрируем таблицей :
В результате анализа получено синтаксическое дерево разбора:
<S> │ ┌─────────<E>─────────┐ │ │ ┌──<T>──┐ <X> │ │ │ <F> ┌─<Y>─┐ "lambda" │ │ │ i * ┌─<T>─┐ │ │ <F> <Y> │ │ i "lambda"
В выходном стеке это дерево представляется в виде:
12 │ <X>,2│ ───┼──────┤ 11 │ <Y>,8│ ───┼──────┤ 10 │ i,9│ ───┼──────┤ 9 │ <F>,8│ ───┼──────┤ 8 │ <T>,6│ ───┼──────┤ 7 │ *,6│ ───┼──────┤ 6 │ <Y>,3│ ───┼──────┤ 5 │ i,4│ ───┼──────┤ 4 │ <F>,3│ ───┼──────┤ 3 │ <T>,2│ ───┼──────┤ 2 │ <E>,1│ ───┼──────┤ 1 │ <S>,0│ ───┴──────┘
|
Последнее изменение этой страницы: 2019-05-07; Просмотров: 311; Нарушение авторского права страницы