LL грамматика

Грамматика C ​ не LL(1): в нижней части показан анализатор, который обработал токены " int v;main(){" и собирается выбрать правило для получения нетерминала " Stmt". Смотрим только на первый токен просмотра вперед" v", он не может решить, какой из двух вариантов " Stmt", чтобы выбрать, поскольку возможны два продолжения ввода. Их можно различить, взглянув на второй токен просмотра вперед (желтый фон).

В теории формального языка LL -грамматика — это контекстно-свободная грамматика , которая может быть проанализирована анализатором LL , который анализирует входные данные слева направо и создает самое левое производное предложение (следовательно, LL по сравнению с анализатором LR) . которое строит крайний правый вывод). Язык, имеющий грамматику LL, называется языком LL . Они образуют подмножества детерминированных контекстно-свободных грамматик (DCFG) и детерминированных контекстно-свободных языков (DCFL) соответственно. Говорят, что данная грамматика или язык «является грамматикой/языком LL» или просто «является LL», чтобы указать, что он принадлежит к этому классу.

Парсеры LL — это парсеры на основе таблиц, аналогичные парсерам LR. В качестве альтернативы LL-грамматики можно охарактеризовать как те, которые могут быть проанализированы с помощью анализатора с прогнозированием — анализатора с рекурсивным спуском без возврата — и их можно легко написать вручную. Эта статья о формальных свойствах LL-грамматик; для синтаксического анализа см. анализатор LL или анализатор рекурсивного спуска .

Формальное определение

Конечный случай

Учитывая натуральное число $k\geq 0$,контекстно -свободная грамматика $G=(V,\Sigma ,R,S)$является LL(k)-грамматикой , если

• для каждой строки символа терминала $w\in \Sigma ^{*}$ длиной до $k$ символы,
• для каждого нетерминального символа $A\in V$, и
• для каждой строки символа терминала $w_{1}\in \Sigma ^{*}$,

существует не более одного производственного правила $r\in R$ так что для некоторых строк терминальных символов $w_{2},w_{3}\in \Sigma ^{*}$,

• строка $w_{1}Aw_{3}$ может быть получен из начального символа $S$,
• $w_{2}$ может быть получено из $A$ после первого применения правила $r$, и
• первый $k$ символы $w$ и из $w_{2}w_{3}$ соглашаться.

Альтернативное, но эквивалентное формальное определение следующее: $G=(V,\Sigma ,R,S)$ является LL(k)-грамматикой , если для произвольных дифференцирований

${\begin{array}{ccccccc}S&\Rightarrow ^{L}&w_{1}A\chi &\Rightarrow &w_{1}\nu \chi &\Rightarrow ^{*}&w_{1}w_{2}w_{3}\\S&\Rightarrow ^{L}&w_{1}A\chi &\Rightarrow &w_{1}\omega \chi &\Rightarrow ^{*}&w_{1}w'_{2}w'_{3},\\\end{array}}$

когда первый $k$ символы $w_{2}w_{3}$ согласен с мнением $w'_{2}w'_{3}$, затем $\nu =\omega$.

Неформально, когда парсер вывел $w_{1}Aw_{3}$, с $A$ его крайний левый нетерминал и $w_{1}$ уже израсходовано со входа, а затем, посмотрев на это $w_{1}$ и смотрю на следующее $k$ символы $w$ текущего ввода синтаксический анализатор может с уверенностью идентифицировать производственное правило $r$ для $A$.

Когда идентификация правила возможна даже без учета прошлых входных данных $w_{1}$, то грамматика называется сильной LL(k)-грамматикой . В формальном определении сильной LL( k ) грамматики универсальный квантор для $w_{1}$ опускается, и $w_{1}$ добавляется к квантору «для некоторых» для $w_{2},w_{3}$.Для каждой LL( k ) грамматики структурно эквивалентную сильную LL( k ) грамматику. можно построить

Класс языков LL( k ) образует строго возрастающую последовательность множеств: LL(0) ⊊ LL(1) ⊊ LL(2) ⊊ …. Можно решить, является ли данная грамматика G LL( k ), но неразрешимо, является ли произвольная грамматика LL( k ) для некоторого k . Также разрешимо, если данная LR( k ) грамматика также является LL( m ) грамматикой для некоторого m .

Каждая LL( k ) грамматика также является LR( k ) грамматикой. Грамматика LL(1) без ε также является грамматикой SLR(1). Грамматика LL(1) с символами, имеющими как пустые, так и непустые производные, также является грамматикой LALR(1). Грамматика LL(1) с символами, имеющими только пустой вывод, может быть или не быть LALR(1).

В LL-грамматиках не может быть правил, содержащих левую рекурсию . Каждую LL( k ) грамматику, свободную от ε, можно преобразовать в эквивалентную LL( k ) грамматику в нормальной форме Грейбаха (которая по определению не имеет правил с левой рекурсией).

Обычный случай

Позволять $\Sigma$ быть терминальным алфавитом. Раздел ​ $\pi$ из $\Sigma ^{*}$ называется регулярным разбиением, если для любого $R\in \pi$ язык $R$ является регулярным.

Позволять $G=(V,\Sigma ,R,S)$ быть контекстно-свободной грамматикой и позволить $\pi =\{R_{1},\dotso ,R_{n}\}$ быть обычным разделом $\Sigma ^{*}$. Мы говорим, что $G$ это LL( $\pi$) грамматика , если для произвольных выводов

${\begin{array}{ccccccc}S&\Rightarrow ^{L}&w_{1}A\chi _{1}&\Rightarrow &w_{1}\nu \chi _{1}&\Rightarrow ^{*}&w_{1}x\\S&\Rightarrow ^{L}&w_{2}A\chi _{2}&\Rightarrow &w_{2}\omega \chi _{2}&\Rightarrow ^{*}&w_{2}y,\\\end{array}}$

такой, что $x\equiv y\mod \pi$ отсюда следует, что $\nu =\omega$.

Грамматика G называется LL-регулярной (LLR), если существует регулярное разбиение $\Sigma ^{*}$ такой, что G есть LL( $\pi$). Язык является LL-регулярным, если он порожден LL-регулярной грамматикой.

Грамматики LLR однозначны и не могут быть леворекурсивными.

Каждая LL( k ) грамматика является LLR. Каждая LL( k )-грамматика детерминирована, но существует LLR-грамматика, которая не является детерминированной. Следовательно, класс грамматик LLR строго больше, чем объединение LL( k ) для каждого k .

Решаемо, будет ли при правильном разбиении $\pi$, данная грамматика — это LL( $\pi$). Однако неясно, является ли произвольная грамматика G LLR. Это связано с тем, что решение вопроса о том, порождает ли грамматика G регулярный язык, которое было бы необходимо для нахождения регулярного разбиения для G , можно свести к проблеме соответствия Поста .

Любая LLR-грамматика является LR-регулярной (LRR, соответствующая эквивалентно для грамматик LR( k ), но существует грамматика LR(1), которая не является LLR.

Исторически грамматики LLR последовали за изобретением грамматик LRR. Учитывая регулярное разбиение, можно построить машину Мура , преобразующую синтаксический анализ справа налево, идентифицируя экземпляры регулярных постановок. Как только это будет сделано, анализатора LL(1) будет достаточно для обработки преобразованных входных данных за линейное время. Таким образом, анализаторы LLR могут обрабатывать класс грамматик, строго больший, чем анализаторы LL( k ), оставаясь при этом одинаково эффективными.Несмотря на это, теория LLR не имеет серьезных приложений. Одна из возможных и очень правдоподобных причин заключается в том, что, хотя существуют генеративные алгоритмы для анализаторов LL( k ) и LR( k ), проблема создания анализатора LLR/LRR неразрешима, если заранее не построить регулярный раздел. Но даже проблема построения подходящего регулярного разбиения по заданной грамматике неразрешима.

Простые детерминированные языки

Контекстно-свободная грамматика называется простой детерминированной . или просто просто , если

• оно находится в нормальной форме Грейбаха (т. е. каждое правило имеет вид $Z\rightarrow aY_{1}\ldots Y_{n},n\geq 0$), и
• разные правые части для одного и того же нетерминала $Z$ всегда начинайте с разных терминалов $a$.

Набор строк называется простым детерминированным или просто простым языком, если он имеет простую детерминированную грамматику.

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

Приложения

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

См. также

• Сравнение генераторов парсеров для списка парсеров LL(k) и LL(*)

Источники

• Битти, Джей Си (1982). «О взаимосвязи между грамматиками LL(1) и LR(1)» (PDF) . Журнал АКМ . 29 (4 октября): 1007–1022. дои : 10.1145/322344.322350 . S2CID   14700480 .
• Хопкрофт, Джон Э.; Уллман, Джеффри Д. (1979). Введение в теорию автоматов, языки и вычисления . Аддисон-Уэсли. ISBN  978-0-201-02988-8 .
• Керниган, Брайан В.; Ричи, Деннис М. (апрель 1988 г.). Язык программирования Си . Серия программного обеспечения Prentice Hall (2-е изд.). Энглвуд Клиффс / Нью-Джерси: Прентис Холл. ISBN  978-013110362-7 .
• Кореняк, AJ; Хопкрофт, Дж. Э. (1966). «Простые детерминированные языки». Конференция IEEE. Рек. 7-я Энн. Симп. по теории коммутации и автоматов (SWAT) . Публикация IEEE. Нет. Том. 16-С-40. стр. 36–46. дои : 10.1109/SWAT.1966.22 .
• Парр, Т.; Фишер, К. (2011). «LL (*): Основа генератора парсера ANTLR» (PDF) . Уведомления ACM SIGPLAN . 46 (6): 425–436. дои : 10.1145/1993316.1993548 .
• Розенкранц, диджей; Стернс, RE (1970). «Свойства детерминированных нисходящих грамматик» . Информация и контроль . 17 (3): 226–256. дои : 10.1016/s0019-9958(70)90446-8 .
• Уэйт, Уильям М.; Гус, Герхард (1984). Конструкция компилятора . Тексты и монографии по информатике. Гейдельберг: Спрингер. ISBN  978-3-540-90821-0 .

Дальнейшее чтение

• Сиппу, Сеппо; Сойсалон-Сойнинен, Эльяс (1990). Теория синтаксического анализа: синтаксический анализ LR(k) и LL(k) . Springer Science & Business Media. ISBN  978-3-540-51732-0 .