Можно ли превратить эту грамматику в LR (1)?

Question

Следующая грамматика генерирует предложения a, a, a, b, b, b, ..., h, b. К сожалению, это не LR (1), поэтому нельзя использовать с такими инструментами, как «yacc».

S -> a comma a. 
S -> C comma b. 
C -> a | b | c | d | e | f | g | h. 

Можно ли преобразовать эту грамматику, чтобы быть LR (1) (или даже LALR (1), LL (K) или LL (1)) без необходимости расширения нетерминальному C и, таким образом, значительно увеличить количество постановок?

Answer 1

Не до тех пор, пока в некотором правиле вы имеете нетерминальную C неизмененную предыдущую запятую.

В этом случае понятно, что синтаксический анализатор не может решить, увидев «a» и имеющий «запятую», чтобы уменьшить или сдвинуть. Таким образом, с C неизменной эта грамматика не является LR (1), как вы сказали.

Но решение лежит в двух фразах: «увидев« a »и« C неизменным ». Вы спросили, есть ли исправление, не расширяется C. Существует нет, но вы могли бы расширить С «немного» путем удаления «а» от С, так как это источник проблемы:

S -> a comma a . 
S -> a comma b . 
S -> C comma b . 
C -> b | c | d | e | f | g | h . 

Таким образом, мы не «значительно» увеличили количество производств.