грамматика английского языка

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

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

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

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

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

когда первые символы согласуются с символами , то . ^{[3] [4]}${\ Displaystyle к}$${\ Displaystyle ш_ {2} ш_ {3}}$${\ Displaystyle ш'_ {2} ш'_ {3}}$${\ Displaystyle \ ню = \ омега}$

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