У меня есть грамматика, и я могу проверить, есть ли LL (1). Однако есть ли способ проверить, является ли язык, сгенерированный грамматикой, LL (1)? И в чем же разница между LL (1) грамматиками и LL (1) языками?
Как определить, является ли язык LL (1)?
Ответ 1
Любая грамматика, которая является 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) для языка, порожденного исходная грамматика (что сложно) или математически доказать, что такой грамматики нет.
Надеюсь, это поможет!