LL-парсер

Нисходящий парсер, который анализирует входные данные слева направо

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

Парсер LL называется парсером LL( k ), если он использует k токенов опережающего просмотра при разборе предложения. Грамматика называется грамматикой LL( k ), если из нее можно построить парсер LL( k ). Формальный язык называется языком LL( k ), если он имеет грамматику LL( k ). Множество языков LL( k ) надлежащим образом содержится в множестве языков LL( k +1) для каждого k  ≥ 0. ^[1] Следствием этого является то, что не все контекстно-свободные языки могут быть распознаны парсером LL( k ).

LL-парсер называется LL-регулярным (LLR), если он анализирует LL-регулярный язык . ^{[ необходимо уточнение ] [2] [3] [4]} Класс LLR-грамматик содержит каждую LL(k)-грамматику для каждого k. Для каждой LLR-грамматики существует LLR-парсер, который анализирует грамматику за линейное время. ^{[ необходима цитата ]}

Два номенклативных типа анализаторов выбросов — LL(*) и LL(finite). Анализатор называется LL(*)/LL(finite), если он использует стратегию анализа LL(*)/LL(finite). ^{[5] [6]} Анализаторы LL(*) и LL(finite) функционально ближе к анализаторам PEG . Анализатор LL(finite) может оптимально анализировать произвольную грамматику LL(k) по количеству предпросмотров и сравнений предпросмотров. Класс грамматик, анализируемых стратегией LL(*), охватывает некоторые контекстно-зависимые языки из-за использования синтаксических и семантических предикатов и не был идентифицирован. Было высказано предположение, что анализаторы LL(*) лучше рассматривать как анализаторы TDPL . ^[7] Вопреки распространенному заблуждению, LL(*)-анализаторы в общем случае не являются LLR-анализаторами и по своей конструкции гарантированно работают хуже в среднем (сверхлинейно по сравнению с линейным временем) и намного хуже в худшем случае (экспоненциально по сравнению с линейным временем).

Грамматики LL, особенно грамматики LL(1), представляют большой практический интерес, поскольку парсеры для этих грамматик легко построить, и многие компьютерные языки разработаны для работы с LL(1) по этой причине. ^[8] Парсеры LL могут быть основаны на таблицах, ^{[ требуется ссылка ]} т.е. похожи на парсеры LR , но грамматики LL также могут быть проанализированы парсерами рекурсивного спуска . Согласно Уэйту и Гусу (1984), ^[9] грамматики LL( k ) были введены Стернсом и Льюисом (1969). ^[10]

Обзор

Для заданной контекстно-свободной грамматики парсер пытается найти самый левый вывод . Приведем пример грамматики : ${\displaystyle G}$

1. ${\displaystyle S\to E}$
2. ${\displaystyle E\to (E+E)}$
3. ${\displaystyle E\to i}$

самый левый вывод для : ${\displaystyle w=((i+i)+i)}$

${\displaystyle S\ {\overset {(1)}{\Rightarrow }}\ E\ {\overset {(2)}{\Rightarrow }}\ (E+E)\ {\overset {(2)}{\Rightarrow }}\ ((E+E)+E)\ {\overset {(3)}{\Rightarrow }}\ ((i+E)+E)\ {\overset {(3)}{\Rightarrow }}\ ((i+i)+E)\ {\overset {(3)}{\Rightarrow }}\ ((i+i)+i)}$

Обычно существует несколько возможностей при выборе правила для расширения самого левого нетерминала. На шаге 2 предыдущего примера парсер должен выбрать, применять ли правило 2 или правило 3:

${\displaystyle S\ {\overset {(1)}{\Rightarrow }}\ E\ {\overset {(?)}{\Rightarrow }}\ ?}$

Чтобы быть эффективным, парсер должен иметь возможность делать этот выбор детерминированно, когда это возможно, без возврата назад. Для некоторых грамматик он может сделать это, подглядывая за непрочитанным вводом (без чтения). В нашем примере, если парсер знает, что следующий непрочитанный символ — , единственное правильное правило, которое можно использовать, — 2. ${\displaystyle (}$

Обычно синтаксический анализатор может предвидеть символы. Однако, если задана грамматика, проблема определения, существует ли синтаксический анализатор для некоторого , который ее распознает, неразрешима. Для каждого существует язык, который не может быть распознан синтаксическим анализатором , но может быть распознан . ${\displaystyle LL(k)}$ ${\displaystyle k}$ ${\displaystyle LL(k)}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle LL(k)}$ ${\displaystyle LL(k+1)}$

Мы можем использовать вышеприведенный анализ, чтобы дать следующее формальное определение:

Пусть будет контекстно-свободной грамматикой и . Мы говорим, что это , тогда и только тогда, когда для любых двух крайних левых выводов: ${\displaystyle G}$ ${\displaystyle k\geq 1}$ ${\displaystyle G}$ ${\displaystyle LL(k)}$

1. ${\displaystyle S\ \Rightarrow \ \cdots \ \Rightarrow \ wA\alpha \ \Rightarrow \ \cdots \ \Rightarrow \ w\beta \alpha \ \Rightarrow \ \cdots \ \Rightarrow \ wu}$
2. ${\displaystyle S\ \Rightarrow \ \cdots \ \Rightarrow \ wA\alpha \ \Rightarrow \ \cdots \ \Rightarrow \ w\gamma \alpha \ \Rightarrow \ \cdots \ \Rightarrow \ wv}$

выполняется следующее условие: префикс строки длины равен префиксу строки длины , что подразумевает . ${\displaystyle u}$ ${\displaystyle k}$ ${\displaystyle v}$ ${\displaystyle k}$ ${\displaystyle \beta \ =\ \gamma }$

В этом определении — начальный символ и любой нетерминал. Уже выведенный ввод , и еще непрочитанный и — строки терминалов. Греческие буквы , и представляют любую строку как терминалов, так и нетерминалов (возможно, пустую). Длина префикса соответствует размеру буфера просмотра вперед, и определение говорит, что этого буфера достаточно, чтобы различать любые два вывода разных слов. ${\displaystyle S}$ ${\displaystyle A}$ ${\displaystyle w}$ ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle \alpha }$ ${\displaystyle \beta }$ ${\displaystyle \gamma }$

Парсер

Парсер представляет собой детерминированный магазинный автомат с возможностью подглядывать за следующими входными символами без чтения. Эту возможность подглядывания можно эмулировать, сохраняя содержимое буфера просмотра вперед в конечном пространстве состояний, поскольку и буфер, и входной алфавит имеют конечный размер. В результате это не делает автомат более мощным, но является удобной абстракцией. ${\displaystyle LL(k)}$ ${\displaystyle k}$

Алфавит стека — это , где: ${\displaystyle \Gamma =N\cup \Sigma }$

• ${\displaystyle N}$— множество нетерминалов;
• ${\displaystyle \Sigma }$набор терминальных (входных) символов со специальным символом конца ввода (EOI) . ${\displaystyle \$}$

Стек парсера изначально содержит начальный символ над EOI: . Во время работы парсер многократно заменяет символ наверху стека: ${\displaystyle [\ S\ \$\ ]}$ ${\displaystyle X}$

• с некоторыми , если и есть правило ; ${\displaystyle \alpha }$ ${\displaystyle X\in N}$ ${\displaystyle X\to \alpha }$
• с (в некоторых обозначениях ), то есть выталкивается из стека, если . В этом случае считывается входной символ , и если , синтаксический анализатор отклоняет входные данные. ${\displaystyle \epsilon }$ ${\displaystyle \lambda }$ ${\displaystyle X}$ ${\displaystyle X\in \Sigma }$ ${\displaystyle x}$ ${\displaystyle x\neq X}$

Если последний символ, удаляемый из стека, — это EOI, то синтаксический анализ успешен; автомат принимает его через пустой стек.

Состояния и функция перехода не заданы явно; они определяются (генерируются) с использованием более удобной таблицы разбора . Таблица обеспечивает следующее отображение:

• строка: символ вершины стека ${\displaystyle X}$
• столбец: содержимое буфера просмотра вперед ${\displaystyle |w|\leq k}$
• ячейка: номер правила для или ${\displaystyle X\to \alpha }$ ${\displaystyle \epsilon }$

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

Конкретный пример

Настраивать

Чтобы объяснить работу синтаксического анализатора LL(1), рассмотрим следующую небольшую грамматику LL(1):

1. С → Ф
2. С → ( С + Ж )
3. Ф → а

и проанализируем следующие входные данные:

( а + а )

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

Каждая ячейка таблицы может указывать максимум на одно правило грамматики (идентифицируемое по его номеру). Например, в таблице анализа для приведенной выше грамматики ячейка для нетерминала 'S' и терминала '(' указывает на правило номер 2:

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

Процедура анализа

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

Таким образом, на первом этапе анализатор считывает входной символ ' ( ' и вершину стека символа 'S'. Инструкция таблицы анализа поступает из столбца, возглавляемого входным символом ' ( ', и строки, возглавляемой вершиной стека символом 'S'; эта ячейка содержит '2', что предписывает анализатору применить правило (2). Анализатор должен переписать 'S' в ' ( S + F ) ' в стеке, удалив 'S' из стека и поместив ')', 'F', '+', 'S', '(' в стек, и это записывает правило номер 2 в выход. Затем стек становится следующим:

[ ( , С, + , Ж, ) , $ ]

На втором этапе синтаксический анализатор удаляет ' ( ' из своего входного потока и из своего стека, поскольку теперь они совпадают. Теперь стек становится следующим:

[ С, + , Ж, ) , $ ]

Теперь парсер имеет ' a' на входном потоке и 'S' на вершине стека. Таблица парсинга предписывает ему применить правило (1) из грамматики и записать правило номер 1 в выходной поток. Стек становится:

[ Ф, + , Ф, ) , $ ]

Теперь парсер имеет ' a' на входном потоке и 'F' на вершине стека. Таблица парсинга предписывает ему применить правило (3) из грамматики и записать правило номер 3 в выходной поток. Стек становится:

[ а , + , Ж, ) , $ ]

Теперь у парсера есть ' a' во входном потоке и ' a' на вершине стека. Поскольку они одинаковы, он удаляет его из входного потока и выталкивает его из вершины стека. Затем у парсера есть ' +' во входном потоке и ' +' на вершине стека, что означает, как и в случае с ' a ', он выталкивается из стека и удаляется из входного потока. Это приводит к следующему:

[ Ф, ) , $ ]

На следующих трех шагах парсер заменит ' F' в стеке на ' a' , запишет правило номер 3 в выходной поток и удалит ' a' и ' )' из стека и входного потока. Таким образом, парсер заканчивается с ' $' как в своем стеке, так и во входном потоке.

В этом случае парсер сообщит, что он принял входную строку, и запишет в выходной поток следующий список номеров правил:

[ 2, 1, 3, 3 ]

Это действительно список правил для самого левого вывода входной строки, который выглядит следующим образом:

С → ( С + Ж ) → ( Ж + Ж ) → ( а + Ж ) → ( а + а )

Реализация парсера на языке C++

Ниже приведена реализация на C++ табличного LL-анализатора для примера языка:

#include <iostream> #include <map> #include <stack>   enum Symbols { // символы: // Терминальные символы: TS_L_PARENS , // ( TS_R_PARENS , // ) TS_A , // a TS_PLUS , // + TS_EOS , // $, в этом случае соответствует '\0' TS_INVALID , // недопустимый токен  // Нетерминальные символы: NTS_S , // S NTS_F // F };/* Преобразует допустимый токен в соответствующий терминальный символ */ Символы lexer ( char c ) { switch ( c ) { case '(' : return TS_L_PARENS ; case ')' : return TS_R_PARENS ; case 'a' : return TS_A ; case '+' : return TS_PLUS ; case '\0' : return TS_EOS ; // конец стека: терминальный символ $ default : return TS_INVALID ; } }                     int main ( int argc , char ** argv ) { using namespace std ;      если ( argc < 2 ) { cout << "использование: \n\t ll '(a+a)'" << endl ; return 0 ; }        // LL-анализатор table, сопоставляет пару <non- terminal , terminal> с парой действий map < Symbols , map < Symbols , int >> table ; stack <Symbols> ss ; // стек символов char * p ; // входной буфер      // инициализируем стек символов ss.push ( TS_EOS ) ; // терминал, $ ss.push ( NTS_S ) ; // нетерминал, S// инициализируем курсор потока символов p = & argv [ 1 ][ 0 ];  // настраиваем таблицу синтаксического анализа table [ NTS_S ][ TS_L_PARENS ] = 2 ; table [ NTS_S ][ TS_A ] = 1 ; table [ NTS_F ][ TS_A ] = 3 ;      while ( ss . size () > 0 ) { if ( lexer ( * p ) == ss . top ()) { cout << "Совпадающие символы: " << lexer ( * p ) << endl ; p ++ ; ss . pop (); } else { cout << "Правило " << table [ ss . top ()][ lexer ( * p )] << endl ; switch ( table [ ss . top ()][ lexer ( * p )]) { case 1 : // 1. S → F ss . pop (); ss . push ( NTS_F ); // F break ;                    случай 2 : // 2. S → ( S + F ) ss.pop ( ); ss.push ( TS_R_PARENS ) ; // ) ss.push ( NTS_F ) ; // F ss.push ( TS_PLUS ) ; // + ss.push ( NTS_S ) ; // S ss.push ( TS_L_PARENS ) ; // ( break ; случай 3 : // 3. F → a ss.pop ( ) ; ss.push ( TS_A ) ; // перерыв ; по умолчанию : cout << "анализ таблицы по умолчанию" << endl ; return 0 ; } } }     cout << "закончен анализ" << endl ;    вернуть 0 ; } 

Реализация парсера на Python

# Все константы индексируются с 0 TERM  =  0 RULE  =  1# Терминалы T_LPAR  =  0 T_RPAR  =  1 T_A  =  2 T_PLUS  =  3 T_END  =  4 T_INVALID  =  5# Нетерминалы N_S  =  0 N_F  =  1# Анализ таблицы table  =  [[  1 ,  - 1 ,  0 ,  - 1 ,  - 1 ,  - 1 ],  [ - 1 ,  - 1 ,  2 ,  - 1 ,  - 1 ,  - 1 ]]ПРАВИЛА  =  [[( ПРАВИЛО ,  N_F )],  [( ТЕРМИН ,  T_LPAR ),  ( ПРАВИЛО ,  N_S ),  ( ТЕРМИН ,  T_PLUS ),  ( ПРАВИЛО ,  N_F ),  ( ТЕРМИН ,  T_RPAR )],  [( ТЕРМИН ,  T_A )]]стек  =  [( ТЕРМИН ,  T_END ),  ( ПРАВИЛО ,  N_S )]def  lexical_analysis ( inputstring :  str )  - >  list :  print ( " Лексический анализ " ) tokens  =  [  ]  for c  in  inputstring  : if  c  ==  "  + " :  tokens.append ( T_PLUS ) elif c == " ( " : tokens.append ( T_LPAR ) elif c == " ) " : tokens.append ( T_RPAR ) elif c == " a " : tokens.append ( T_A ) else : tokens.append ( T_INVALID ) tokens.append ( T_END ) print ( tokens ) return tokens                     def  syntactic_analysis ( tokens :  list )  ->  None :  print ( "Синтаксический анализ " )  position  =  0  while  len ( stack )  >  0 :  ( stype ,  svalue )  =  stack . pop ()  token  =  tokens [ position ]  if  stype  ==  TERM :  if  svalue  ==  token :  position  +=  1  print ( "pop " ,  svalue )  if  token  ==  T_END :  print ( "input Accepted " )  else :  print ( "неправильный термин на входе: " ,  token )  break  elif  stype  ==  RULE :  print ( "svalue " ,  svalue ,  "token " ,  token )  rule  =  table [ svalue ][ token ]  print ( "rule " ,  rule )  for  r  in  reversed ( RULES [ rule ]):  stack . добавить ( r )  распечатать ( "стек" ,  стек )входная_строка  =  "(a+a)" синтаксический_анализ ( лексический_анализ ( входная_строка ))

Замечания

Как видно из примера, синтаксический анализатор выполняет три типа шагов в зависимости от того, является ли вершина стека нетерминалом, терминалом или специальным символом $ :

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

Эти шаги повторяются до тех пор, пока анализатор не остановится, после чего он либо полностью проанализирует входные данные и запишет крайний левый вывод в выходной поток, либо сообщит об ошибке.

Построение таблицы синтаксического анализа LL(1)

Чтобы заполнить таблицу синтаксического анализа, нам нужно установить, какое правило грамматики должен выбрать синтаксический анализатор, если он видит нетерминал A наверху своего стека и символ a во входном потоке. Легко видеть, что такое правило должно иметь вид A → w и что язык, соответствующий w, должен иметь по крайней мере одну строку, начинающуюся с a . Для этой цели мы определяем First-set of w , записанный здесь как Fi ( w ), как множество терминалов, которые могут быть найдены в начале некоторой строки в w , плюс ε, если пустая строка также принадлежит w . Учитывая грамматику с правилами A ₁ → w ₁ , …, An → w _n , мы можем вычислить Fi ( w _i ) и Fi ( A _i ) для каждого правила следующим образом _:

1. инициализируем каждый Fi ( A _i ) пустым множеством
2. добавить Fi( w _i ) к Fi ( A _i ) для каждого правила A _i → w _i ​​, где Fi определяется следующим образом:
   • Fi( aw' ) = { a } для каждого терминала a
   • Fi( Aw' ) = Fi ( A ) для каждого нетерминала A с ε, не принадлежащего Fi ( A )
   • Fi( Aw' ) = ( Fi ( A ) \ { ε }) ∪ Fi( w' ) для каждого нетерминала A с ε в Fi ( A )
   • Фи(ε) = { ε }
3. добавить Fi( w _i ) к Fi ( A _i ) для каждого правила A _i → w _i
4. повторяйте шаги 2 и 3 до тех пор, пока все наборы Fi не останутся прежними.

Результатом является решение с наименьшей фиксированной точкой для следующей системы:

• Fi ( A ) ⊇ Fi ( w ) для каждого правила A → w
• Fi ( a ) ⊇ { a }, для каждого терминала a
• Fi ( w ₀ w ₁ ) ⊇ Fi ( w ₀ )· Fi ( w ₁ ), для всех слов w ₀ и w ₁
• Фи (ε) ⊇ {ε}

где для наборов слов U и V усеченное произведение определяется как , а w:1 обозначает начальный префикс длины 1 слов w длиной 2 или более, или само w, если w имеет длину 0 или 1. ${\displaystyle U\cdot V=\{(uv):1\mid u\in U,v\in V\}}$

К сожалению, First-sets недостаточны для вычисления таблицы синтаксического анализа. Это связано с тем, что правая часть w правила в конечном итоге может быть переписана в пустую строку. Поэтому синтаксический анализатор также должен использовать правило A → w , если ε находится в Fi ( w ) и он видит во входном потоке символ, который может следовать за A . Поэтому нам также нужен Follow-set для A , записанный здесь как Fo ( A ), который определяется как набор терминалов a такой, что существует строка символов αAaβ , которая может быть получена из начального символа. Мы используем $ как специальный терминал, указывающий конец входного потока, и S как начальный символ.

Вычисление множеств следования для нетерминалов в грамматике можно выполнить следующим образом:

1. инициализируем Fo ( S ) с помощью { $ } и все остальные Fo ( A _i ) с помощью пустого множества
2. если существует правило вида A _j → wA _i w' , то
   • если терминал a находится в Fi ( w' ), то добавьте a к Fo ( A _i )
   • если ε находится в Fi ( w' ), то добавьте Fo ( A _j ) к Fo ( A _i )
   • если w' имеет длину 0, то добавьте Fo ( A _j ) к Fo ( A _i )
3. повторяйте шаг 2 до тех пор, пока все наборы Fo не останутся прежними.

Это обеспечивает решение с наименьшей фиксированной точкой для следующей системы:

• Fo ( S ) ⊇ { $ }
• Fo ( A ) ⊇ Fi ( w )· Fo ( B ) для каждого правила вида B → ... A w

Теперь мы можем точно определить, какие правила будут появляться в таблице разбора. Если T [ A , a ] обозначает запись в таблице для нетерминала A и терминала a , то

T [ A , a ] содержит правило A → w тогда и только тогда, когда

а находится в Fi ( w ) или

ε находится в Fi ( w ), а a находится в Fo ( A ).

Эквивалентно: T [ A , a ] содержит правило A → w для каждого a ∈ Fi ( w )· Fo ( A ).

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

Построение LL(к) таблица разбора

Конструкция для анализаторов LL(1) может быть адаптирована к LL( k ) для k > 1 со следующими изменениями:

• усеченное произведение определяется как , где w:k обозначает начальный префикс длины k слов длины > k, или w, сам по себе, если w имеет длину k или меньше, ${\displaystyle U\cdot V=\{(uv):k\mid u\in U,v\in V\}}$
• Fo ( S ) = { $ ^k }
• Применим Fi (αβ) = Fi (α) Fi (β) также на шаге 2 построения Fi , приведенного для LL(1). ${\displaystyle \cdot }$
• На шаге 2 построения Fo для A _j → wA _i w' просто прибавляем Fi ( w' ) Fo ( A _j ) к Fo ( A _i ). ${\displaystyle \cdot }$

где вход дополнен k конечными маркерами $ , чтобы полностью учесть k контекста просмотра вперед. Этот подход исключает особые случаи для ε и может быть применен в равной степени хорошо в случае LL(1).

До середины 1990-х годов было широко распространено мнение, что парсинг LL( k ^{) [ прояснить ]} (для k > 1) был непрактичным, ^{[11] : 263–265} поскольку таблица парсера имела бы экспоненциальный размер по k в худшем случае. Это восприятие постепенно изменилось после выпуска Purdue Compiler Construction Tool Set около 1992 года, когда было продемонстрировано, что многие языки программирования могут быть эффективно проанализированы парсером LL( k ) без запуска наихудшего поведения парсера. Более того, в некоторых случаях парсинг LL возможен даже с неограниченным опережением. Напротив, традиционные генераторы парсеров, такие как yacc, используют таблицы парсеров LALR(1) для построения ограниченного парсера LR с фиксированным опережением на один токен.

Конфликты

Как описано во введении, парсеры LL(1) распознают языки, имеющие грамматики LL(1), которые являются особым случаем контекстно-свободных грамматик; парсеры LL(1) не могут распознавать все контекстно-свободные языки. Языки LL(1) являются собственным подмножеством языков LR(1), которые, в свою очередь, являются собственным подмножеством всех контекстно-свободных языков. Для того чтобы контекстно-свободная грамматика была грамматикой LL(1), не должно возникать определенных конфликтов, которые мы описываем в этом разделе.

Терминология

Пусть A — нетерминал. FIRST( A ) — это (определено как) множество терминалов, которые могут появляться в первой позиции любой строки, полученной из A . FOLLOW( A ) — это объединение по: ^[12]

1. FIRST( B ), где B — любой нетерминал, который следует непосредственно за A в правой части правила производства .
2. FOLLOW( B ), где B — любой заголовок правила формы B → wA .

LL(1) конфликты

Существует два основных типа конфликтов LL(1):

ПЕРВЫЙ/ПЕРВЫЙ конфликт

Наборы FIRST двух различных правил грамматики для одного и того же нетерминала пересекаются. Пример конфликта LL(1) FIRST/FIRST:

С -> Э | Э 'а'Е -> 'б' | ε

FIRST( E ) = { b , ε} и FIRST( E a ) = { b , a }, поэтому при построении таблицы возникает конфликт в терминальной части b правила производства S .

Особый случай: левая рекурсия

Левая рекурсия вызовет конфликт FIRST/FIRST со всеми альтернативами.

E -> E '+' термин | alt1 | alt2

Конфликт ПЕРВЫЙ/ПОСЛЕДУЮЩИЙ

Наборы правил грамматики FIRST и FOLLOW перекрываются. При пустой строке (ε) в наборе FIRST неизвестно, какую альтернативу выбрать. Пример конфликта LL(1):

С -> А 'а' 'б'А -> 'а' | ε

ПЕРВЫЙ набор A — это { a , ε}, а ПОСЛЕДУЮЩИЙ набор — это { a }.

Решения конфликтов LL(1)

Левый факторинг

Обычный левый множитель «выносится за скобки».

А -> X | XYZ

становится

А -> ХБB -> YZ | ε

Может применяться, когда две альтернативы начинаются с одного и того же символа, например, в случае конфликта FIRST/FIRST.

Другой пример (более сложный) с использованием приведенного выше примера конфликта FIRST/FIRST:

С -> Э | Э 'а'Е -> 'б' | ε

становится (сливаясь в один нетерминал)

S -> 'б' | ε | 'б' 'а' | 'а'

затем через левое факторирование становится

С -> 'б' Э | ЭЕ -> 'а' | ε

Замена

Подстановка правила в другое правило для устранения косвенных или FIRST/FOLLOW конфликтов. Обратите внимание, что это может вызвать конфликт FIRST/FIRST.

Удаление левой рекурсии

См. ^[13]

Для общего метода см. удаление левой рекурсии . Простой пример удаления левой рекурсии: Следующее правило производства имеет левую рекурсию на E

Э -> Э '+' ТЭ -> Т

Это правило — не что иное, как список T, разделенных знаком '+'. В регулярном выражении форма T ('+' T)*. Таким образом, правило можно переписать как

Э -> ТЗZ -> '+' ТЗZ -> ε

Теперь нет левой рекурсии и конфликтов ни по одному из правил.

Однако не все контекстно-свободные грамматики имеют эквивалентную LL(k)-грамматику, например:

С -> А | БА -> 'а' А 'б' | εБ -> 'а' Б 'б' 'б' | ε

Можно показать, что не существует LL(k)-грамматики, принимающей язык, порождаемый этой грамматикой.

Смотрите также

• Сравнение генераторов парсеров
• Дерево разбора
• Анализ сверху вниз
• Анализ снизу вверх

Примечания

1. Розенкранц, DJ; Стернс, RE (1970). «Свойства детерминированных грамматик сверху вниз». Информация и управление . 17 (3): 226–256. doi : 10.1016/s0019-9958(70)90446-8 .
2. Ярзабек, Станислав; Кравчик, Томаш (1974). «LL-Регулярные грамматики». Instytutu Maszyn Matematycznych : 107–119.
3. Ярзабек, Станислав; Кравчик, Томаш (ноябрь 1975 г.). «LL-Регулярные грамматики». Письма об обработке информации . 4 (2): 31–37. дои : 10.1016/0020-0190(75)90009-5.
4. Дэвид А. Поплавски (август 1977 г.). Свойства LL-регулярных языков (технический отчет). Университет Пердью , кафедра компьютерных наук.
5. Парр, Теренс и Фишер, Кэтлин (2011). «LL (*) основа генератора синтаксического анализатора ANTLR». ACM SIGPLAN Notices . 46 (6): 425–436. doi :10.1145/1993316.1993548.{{cite journal}}: CS1 maint: несколько имен: список авторов ( ссылка )
6. Белчак, Питер (2020). «Стратегия анализа LL(finite) для оптимального анализа LL(k)». arXiv : 2010.07874 [cs.PL].
7. Форд, Брайан (2004). «Анализ грамматик выражений: синтаксическая основа на основе распознавания». Уведомления ACM SIGPLAN . doi :10.1145/982962.964011.
8. Пэт Терри (2005). Компиляция с C# и Java. Pearson Education. С. 159–164. ISBN 9780321263605.
9. Уильям М. Уэйт и Герхард Гус (1984). Построение компилятора . Тексты и монографии по информатике. Гейдельберг: Springer. ISBN 978-3-540-90821-0.Здесь: Раздел 5.3.2, стр. 121-127; в частности, стр. 123.
10. Ричард Э. Стернс и П. М. Льюис (1969). «Грамматики свойств и табличные машины». Информация и управление . 14 (6): 524–549. doi : 10.1016/S0019-9958(69)90312-X .
11. Фрицсон, Питер А. (23 марта 1994 г.). Compiler Construction: 5-я международная конференция, CC '94, Эдинбург, Великобритания, 7–9 апреля 1994 г. Труды . Springer Science & Business Media. ISBN 978-3-540-57877-2.
12. "LL Grammars" (PDF) . Архивировано (PDF) из оригинала 2010-06-18 . Получено 2010-05-11 .
13. Современный дизайн компилятора, Грюн, Бал, Джейкобс и Лангендоен

Внешние ссылки

• Учебник по реализации парсеров LL(1) в C# (архив)
• Симулятор синтаксического анализа Этот симулятор используется для генерации таблиц синтаксического анализа LL(1) и решения упражнений книги.
• Теоретическое сравнение грамматик LL и LR
• Теория анализа LL(k)