В информатике рекурсивный спусковой анализатор — это разновидность нисходящего синтаксического анализатора, построенного из набора взаимно рекурсивных процедур (или нерекурсивного эквивалента), где каждая такая процедура реализует один из нетерминалов грамматики . Таким образом, структура полученной программы точно отражает структуру грамматики, которую она распознает. [ 1] [2]
Предиктивный синтаксический анализатор — это рекурсивный спусковой синтаксический анализатор, который не требует возврата . [3] Предиктивный синтаксический анализ возможен только для класса грамматик LL( k ) , которые являются контекстно-свободными грамматиками , для которых существует некоторое положительное целое число k , позволяющее рекурсивному спусковому синтаксическому анализатору решать, какую продукцию использовать, исследуя только следующие k токенов входных данных. Поэтому грамматики LL( k ) исключают все неоднозначные грамматики , а также все грамматики, содержащие левую рекурсию . Любая контекстно-свободная грамматика может быть преобразована в эквивалентную грамматику, которая не имеет левой рекурсии, но удаление левой рекурсии не всегда дает грамматику LL( k ). Предиктивный синтаксический анализатор работает за линейное время .
Рекурсивный спуск с откатом назад — это метод, который определяет, какую продукцию использовать, пробуя каждую продукцию по очереди. Рекурсивный спуск с откатом назад не ограничивается грамматиками LL( k ), но не гарантирует завершения, если грамматика не является LL( k ). Даже когда они завершаются, парсеры, использующие рекурсивный спуск с откатом назад, могут потребовать экспоненциальное время .
Хотя предиктивные парсеры широко используются и часто выбираются при написании парсера вручную, программисты часто предпочитают использовать парсер на основе таблиц, созданный генератором парсеров , [ требуется цитата ] либо для языка LL( k ), либо используя альтернативный парсер, такой как LALR или LR . Это особенно актуально, если грамматика не находится в форме LL( k ) , поскольку требуется преобразование грамматики в LL, чтобы сделать ее пригодной для предиктивного парсинга. Предиктивные парсеры также могут быть сгенерированы автоматически с помощью таких инструментов, как ANTLR .
Предиктивные синтаксические анализаторы можно изобразить с помощью диаграмм переходов для каждого нетерминального символа, где ребра между начальным и конечным состояниями помечены символами (терминалами и нетерминалами) правой стороны правила продукций. [4]
Следующая EBNF -подобная грамматика (для языка программирования PL/0 Никлауса Вирта , из книги Алгоритмы + Структуры данных = Программы ) представлена в форме LL(1) :
программа = блок "." . блок = [ "const" идент "=" число { "," идент "=" число } ";" ] [ "var" идент { "," идент } ";" ] { "процедура" идент ";" блок ";" } оператор . оператор = идент ":=" выражение | "вызов" идент | "начало" оператор { ";" оператор } "конец" | "если" условие "тогда" оператор | "пока" условие "до" оператор . условие = "нечетное" выражение | выражение ( "=" | "#" | "<" | "<=" | ">" | ">=" ) выражение . выражение = [ "+" | "-" ] термин {( "+" | "-" ) термин } . термин = фактор {( "*" | "/" ) фактор } . фактор = идент | число | "(" выражение ")" .Терминалы выражены в кавычках. Каждый нетерминал определяется правилом в грамматике, за исключением ident и number , которые, как предполагается, определены неявно.
Далее следует реализация рекурсивного синтаксического анализатора спуска для вышеуказанного языка на языке C. Синтаксический анализатор считывает исходный код и завершает работу с сообщением об ошибке, если код не удается проанализировать, и завершает работу без уведомления, если код распознается правильно.
Обратите внимание, насколько точно предиктивный синтаксический анализатор ниже отражает грамматику выше. Для каждого нетерминала в грамматике есть процедура. Синтаксический анализ выполняется сверху вниз до тех пор, пока не будет обработан последний нетерминал. Фрагмент программы зависит от глобальной переменной sym , которая содержит текущий символ из ввода, и функции nextsym , которая обновляет sym при вызове.
Реализации функций nextsym и error для простоты опущены.
typedef enum { ident , number , lparen , rparen , times , slash , plus , minus , eql , neq , lss , leq , gtr , geq , callsym , beginsym , точка с запятой , endsym , ifsym , whilesym , become , thensym , dosym , constsym , comma , varsym , procsym , period , oddsym } Символ ; Символ sym ; void nextsym ( void ); void error ( const char msg []); int accept ( Symbol s ) { if ( sym == s ) { nextsym (); return 1 ; } return 0 ; } int expect ( Symbol s ) { if ( accept ( s )) return 1 ; error ( "ожидаем: неожиданный символ" ); return 0 ; } void factor ( void ) { if ( accept ( ident )) { ; } else if ( accept ( number )) { ; } else if ( accept ( lparen )) { expression (); expect ( rparen ); } else { error ( "factor: синтаксическая ошибка" ); nextsym (); } } void term ( void ) { factor (); while ( sym == times || sym == slash ) { nextsym (); factor (); } } void выражение ( void ) { if ( sym == plus || sym == minus ) nextsym (); term (); while ( sym == plus || sym == minus ) { nextsym (); term (); } } void condition ( void ) { if ( accept ( oddsym )) { expression (); } else { expression (); if ( sym == eql || sym == neq || sym == lss || sym == leq || sym == gtr || sym == geq ) { nextsym (); expression (); } else { error ( "условие: недопустимый оператор" ); nextsym (); } } } void statement ( void ) { if ( accept ( ident )) { expect ( становится ); expression (); } else if ( accept ( callsym )) { expect ( ident ); } else if ( accept ( beginsym )) { do { statement (); } while ( accept ( setempolon )); expect ( endsym ); } else if ( accept ( ifsym )) { condition (); expect ( thensym ); statement (); } else if ( accept ( whilesym )) { condition (); expect ( dosym ); statement (); } else { error ( "statement: syntax error" ); nextsym (); } } void block ( void ) { if ( accept ( constsym )) { do { expect ( ident ); expect ( eql ); expect ( number ); } while ( accept ( comma )); expect ( точка с запятой ); } if ( accept ( varsym )) { do { expect ( ident ); } while ( accept ( comma )); expect ( точка с запятой ); } while ( accept ( procsym )) { expect ( ident ); expect ( точка с запятой ); block (); expect ( точка с запятой ); } statement (); } пустая программа ( void ) { nextsym (); block (); expect ( period ); } Некоторые генераторы парсеров рекурсивного спуска: