Является ли эта грамматика (для небольшого подмножества Lua) неоднозначной?

У меня есть следующая грамматика, которая является небольшим подмножеством "Полный синтаксис Lua" :

chunk -> | chunk stat.
stat ->  var `=´ exp.
var ->  Name | exp `[´ exp `]´.
exp -> var | exp `(´ exp `)´ | `(´ exp `)´.

Согласно инструменту контекстно-свободной грамматики, эта грамматика не LR(1) и (следовательно?) не LALR(1), SLR(1), LR(0) или LL(1).

Является ли эта грамматика двусмысленной? Если да, не могли бы вы привести пример двусмысленного предложения? Если нет, есть ли веская причина, почему это не LR(1)?

Правка. Немного упрощенная грамматика с той же проблемой:

stat ->  exp | exp var.
var ->  Name | exp `[´ exp `]´.
exp -> var | exp `(´ exp `)´ | `(´ exp `)´.

Редактировать 2: Спасибо Михалу Богуславеку за пример предложения, неоднозначного по отношению ко второй грамматике. К сожалению, это предложение напрямую не приводит к двусмысленности с первой грамматикой.

Однако если бы первое правило второй грамматики было изменено на stat -> exp var., двусмысленное предложение привело бы к неоднозначности с первой грамматикой. Идея Михала может быть расширена для создания такого предложения: exp '(' exp ')' '(' exp ')' '[' exp ']'.


parsing lua compiler-construction lr context-free-grammar
person user200783    schedule 17.07.2016    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Например, эта последовательность неоднозначна по ИМО:

exp '(' exp ')' '[' exp ']'

Это либо:

    exp '[' exp ']'
   /   \
 exp  '(' exp ')'

Or:

    exp     var
          /    \
        exp  '[' exp ']'
         |
    '(' exp ')'
person Michal Bohuslávek    schedule 17.07.2016