Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология
Образование Политология Производство Психология Стандартизация Технологии


Cинтаксический анализ для LL(1)-грамматики



 Алгоритм синтаксического анализа на основе LL(K)-грамматики относится к классу алгоритмов нисходящего разбора.

 Строкам управляющей таблицы М для грамматики G(V,T,P,S) /1/ ставятся в соответствие элементы множества {VUTU$} ($-маркер дна стека), столбцам - элементы множества {T U "lambda"}("lambda" - пустая строка). Перед началом работы алгоритма в рабочий стек заносятся символы $ и S. Возможные значения элементов таблицы и их интерпретация алгоритмом разбора приведены в таблице 1.

 

аблица 1.

N п/п Значение элемента таблицы Интерпретация алгоритмом разбора
1 Номер i порождающего правила грамматики Удаление символа из стека; запись этого выходной стек; запись части правила номер i в рабочий стек справа на лево начиная с последнего символа
2 "сдвиг" Удаление символа из рабочего стека; запись его в выходной стек; считывание следующего символа входной цепочки    
3 "допуск" Конец работы                
4 "ошибка"          Вывод сообщения об ошибке; конец работы             

 

Для построения управляющей таблицы М по заданной 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 + * $
<S> 1      
<E> 2      
<T> 4      
<F> 6      
<X>   3   7
<Y>   8 5 8
i свдвиг      
+   свдвиг    
*     свдвиг  
$       допуск

 

Незаполненные элементы таблицы имеют значение "ошибка". Проанализируем входную цепочку i*i с помощью алгоритма LL(1)-анализатора. При этом, для облегчения формирования выходного стека, при записи символа в рабочий стек будем снабжать его указателем на символ, являющийся его предком в синтаксическом дереве разбора. Процесс анализа проиллюстрируем таблицей :

 

Рабочий стек Вх.символ М(A,a)
<S>,0  $   i 1
<E>,1  $    i 2
<T>,2  <X>,2  $    I 4
<F>,3   <Y>,3   <X>,2  $     i 6
i,4   <Y>,3  <X>,2  $     i «сдвиг»
<Y>,3  <X>,2 $    * 5
*,6   <T>,6 <X>,2  $    * «сдвиг»
<T>,6  <X>,2   $     i 4
<F>,8 <Y>,8 <X>,2  $   i 6
i,9  <Y>,8 <X>,2  $    i «сдвиг»
<Y>,8 <X>,2  $    l 8
<X>,2  $    l 7
$ l «допуск»

 

В результате анализа получено синтаксическое дерево разбора:

 

                            <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; Просмотров: 307; Нарушение авторского права страницы


lektsia.com 2007 - 2024 год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! (0.023 с.)
Главная | Случайная страница | Обратная связь