Как определить, является ли язык LL (1)? - PullRequest
13 голосов
/ 20 августа 2011

У меня есть грамматика, и я могу проверить, является ли LL (1).Однако есть ли способ проверить, является ли язык, сгенерированный грамматикой, LL (1)?И чем именно отличается грамматика LL (1) от языков LL (1)?

1 Ответ

15 голосов
/ 20 августа 2011

Любая грамматика LL (1) определяет язык LL (1). По определению, язык - это LL (1), если существует некоторая грамматика, которая генерирует его, которая является LL (1), поэтому тот факт, что у вас есть грамматика LL (1) для языка, автоматически означает, что язык является LL (1). .

Чтобы уточнить, язык - это набор строк, и грамматика для этого языка является средством описания этого языка. Некоторые языки имеют грамматику LL (1), а другие нет. Однако тот факт, что грамматика не является LL (1), не означает, что язык, который она описывает, не является. Например, рассмотрим следующую грамматику:

A -> ab | ac

Эта грамматика не является LL (1), потому что она содержит конфликт FIRST / FIRST при попытке предсказать производство для A при просмотре терминала a. Однако он описывает язык LL (1), поскольку язык также описывается грамматикой

A -> aX
X -> b | c

Таким образом, язык, генерируемый этими грамматиками (который содержит только ab и ac), действительно является LL (1).

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

Надеюсь, это поможет!

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...