2

У меня есть следующие грамматики, которая представляет собой небольшое подмножество "The Complete Syntax of Lua":Является ли эта грамматика (для небольшого подмножества Lua) двусмысленной?

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

Согласно a context-free grammar tool, эта грамматика не является 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: Благодаря Михал Bohuslávek для примера предложения, которое является неоднозначным относительно второй грамматики. К сожалению, предложение не приводит непосредственно к двусмысленности с первой грамматикой.

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

ответ

1

Например эта последовательность IMO неоднозначным:

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

Это либо:

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

Или:

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

 Смежные вопросы

  • Нет связанных вопросов^_^