LL грамматика - LL grammar

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

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

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

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

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

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

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

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

Струна ${ displaystyle w_ {1} AW_ {3}}$ может быть получено из начального символа ${ displaystyle S}$ ,
${ displaystyle w_ {2}}$ может быть получено из ${ displaystyle A}$ после первого применения правила ${ displaystyle r}$ , и
первый ${ displaystyle k}$ символы ${ displaystyle w}$ и из ${ displaystyle w_ {2} w_ {3}}$ согласны.^[2]

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

${ displaystyle { 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} ш '_ {3}, конец {массив}}}$

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

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

Когда идентификация правила возможна даже без учета прошлого ввода ${ displaystyle w_ {1}}$ , то грамматика называется сильная LL (k) грамматика.^[5] В формальном определении сильной ЛЛ (k) грамматика, универсальный квантор для ${ displaystyle w_ {1}}$ опущено, и ${ displaystyle w_ {1}}$ добавляется к квантификатору "для некоторых" для ${ displaystyle w_ {2}, w_ {3}}$ .Для каждого LL (k) грамматика, структурно эквивалентная сильная LL (k) грамматика может быть построена.^[6]

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

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

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

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

Позволять ${ displaystyle Sigma}$ быть конечным алфавитом. Подмножество ${ Displaystyle Sigma ^ {*}}$ это обычный набор если это обычный язык над ${ displaystyle Sigma}$ . А раздел ${ displaystyle pi}$ из ${ Displaystyle Sigma ^ {*}}$ называется обычный раздел если для каждого ${ Displaystyle R in pi}$ набор ${ displaystyle R}$ регулярно.

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

${ displaystyle { 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, конец {массив}}}$

такой, что ${ Displaystyle х эквив у мод пи}$ следует, что ${ displaystyle nu = omega}$ . ^[12]

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

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

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

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

Каждая грамматика LLR является LR-регулярной (LRR, соответствующий эквивалент для LR (k) грамматики), но существует LR (1) грамматика, которая не является LLR.^[14]

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

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

Контекстно-свободная грамматика называется простой детерминированный,^[15] или просто просто,^[16] если

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

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

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

Приложения

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

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

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

Примечания

^ Керниган и Ричи 1988, Приложение A.13 «Грамматика», стр.193 и далее. В верхней части изображения показан упрощенный отрывок в EBNF -подобное обозначение ..
^ Розенкранц и Стернс (1970, п. 227). Def.1. Авторы дела не рассматривают k=0.
^ куда " ${ displaystyle Rightarrow ^ {L}}$ "обозначает выводимость крайними левыми выводами, а ${ displaystyle w_ {1}, w_ {2}, w_ {3}, w '_ {2}, w' _ {3} in Sigma ^ {*}}$ , ${ displaystyle A in V}$ , и ${ Displaystyle чи, ню, омега в ( сигма чашка V) ^ {*}}$
^ Уэйт и Гус (1984), п. 123) Защ. 5,22
^ Розенкранц и Стернс (1970, п. 235) Защита 2
^ Розенкранц и Стернс (1970, п. 235) Теорема 2.
^ Розенкранц и Стернс (1970, п. 246-247): Использование " ${ displaystyle +}$ "обозначать" или ", набор строк ${ displaystyle {a ^ {n} (b ^ {k} d + b + cc) ^ {n}: n geq 1 }}$ имеет ${ Displaystyle LL (к + 1)}$ , но нет ε-свободных ${ Displaystyle LL (к)}$ грамматика, для каждого ${ Displaystyle к geq 1}$ .
^ Розенкранц и Стернс (1970, стр. 254–255).
^ Битти (1982)
^ Розенкранц и Стернс (1970, с. 241) Лемма 5
^ Розенкранц и Стернс (1970, п. 242) Теорема 4.
^ Поплавский, Дэвид (1977). «Свойства LL-регулярных языков». Университет Пердью. Цитировать журнал требует | журнал = (помощь)
^ Дэвид А. Поплавски (август 1977 г.). Свойства LL-регулярных языков (Технический отчет). Университет Пердью, Департамент компьютерных наук.
^ Дэвид А. Поплавски (август 1977 г.). Свойства LL-регулярных языков (Технический отчет). Университет Пердью, Департамент компьютерных наук.
^ ^а ^б Кореняк и Хопкрофт (1966)
^ ^а ^б Хопкрофт и Ульман (1979), п. 229) Упражнение 9.3.
^ Розенкранц и Стернс (1970, п. 243)

Источники

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

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

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

[FOOTNOTEKernighanRitchie1988Appendix_A.13_"Grammar",_p.193_ff._The_top_image_part_shows_a_simplified_excerpt_in_an_[[EBNF]]-like_notation.-1] Керниган и Ричи 1988, Приложение A.13 «Грамматика», стр.193 и далее. В верхней части изображения показан упрощенный отрывок в EBNF -подобное обозначение ..

[2] Розенкранц и Стернс (1970, п. 227). Def.1. Авторы дела не рассматривают k=0.

[3] куда " ${ displaystyle Rightarrow ^ {L}}$ "обозначает выводимость крайними левыми выводами, а ${ displaystyle w_ {1}, w_ {2}, w_ {3}, w '_ {2}, w' _ {3} in Sigma ^ {*}}$ , ${ displaystyle A in V}$ , и ${ Displaystyle чи, ню, омега в ( сигма чашка V) ^ {*}}$

[4] Уэйт и Гус (1984), п. 123) Защ. 5,22

[5] Розенкранц и Стернс (1970, п. 235) Защита 2

[6] Розенкранц и Стернс (1970, п. 235) Теорема 2.

[7] Розенкранц и Стернс (1970, п. 246-247): Использование " ${ displaystyle +}$ "обозначать" или ", набор строк ${ displaystyle {a ^ {n} (b ^ {k} d + b + cc) ^ {n}: n geq 1 }}$ имеет ${ Displaystyle LL (к + 1)}$ , но нет ε-свободных ${ Displaystyle LL (к)}$ грамматика, для каждого ${ Displaystyle к geq 1}$ .

[8] Розенкранц и Стернс (1970, стр. 254–255).

[9] Битти (1982)

[10] Розенкранц и Стернс (1970, с. 241) Лемма 5

[11] Розенкранц и Стернс (1970, п. 242) Теорема 4.

[12] Поплавский, Дэвид (1977). «Свойства LL-регулярных языков». Университет Пердью. Цитировать журнал требует | журнал = (помощь)

[13] Дэвид А. Поплавски (август 1977 г.). Свойства LL-регулярных языков (Технический отчет). Университет Пердью, Департамент компьютерных наук.

[14] Дэвид А. Поплавски (август 1977 г.). Свойства LL-регулярных языков (Технический отчет). Университет Пердью, Департамент компьютерных наук.

[Korenjak.Hopcroft.1966-15] а ^б Кореняк и Хопкрофт (1966)

[Hopcroft.Ullman.1979.Exc.9.3-16] а ^б Хопкрофт и Ульман (1979), п. 229) Упражнение 9.3.

[17] Розенкранц и Стернс (1970, п. 243)

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]