Зубр: сдвиг уменьшить конфликт - PullRequest
Новая
       32

Зубр: сдвиг уменьшить конфликт

4 голосов
/ 21 марта 2011

Мне кажется, у меня проблемы с пониманием того, как сдвиг уменьшает конфликты. Я понимаю, что зубры могут смотреть вперед на один, поэтому я не понимаю, почему у меня проблема.

На моем языке список определяется как набор чисел или списков между []. Например, [] [1] [1 2] [1 [2] 3] - все допустимые списки.

Вот определения, которые вызывают проблемы 

 value: num 
    | stringValue
    | list          
    ;

list: LEFTBRACE RIGHTBRACE  
    | LEFTBRACE list RIGHTBRACE 
    | num list          
    | RIGHTBRACE            
    ;

Конфликт происходит из числа, он не знает погоду, чтобы сместить по правилу списка или уменьшить по правилу значения. Я запутался, потому что он не может проверить, следует ли список за номером?

Любое подстрекательство к тому, как мне следует поступить, будет с благодарностью.

Ответы [ 2 ]

6 голосов
/ 21 марта 2011

Я думаю, я бы определил вещи по-другому, таким образом, чтобы избежать проблемы, с которой нужно начать, что-то вроде: 

value: num
     | stringvalue
     | list
     ;

items:
     | items value
     ;

list: LEFTBRACE items RIGHTBRACE;

Редактировать: Отделение списков чисел от списков строк не может быть сделано чисто, если вы не удалите пустые списки. Возникающая проблема заключается в том, что вы хотите разрешить включение пустого списка в список чисел или списка строк, но просмотр самого пустого списка не позволяет анализатору решить, какой именно. Например:

[[] [] [] [] [] [] [] [] 1]

Чтобы выяснить, что это за список, парсер должен смотреть вперед до 1 - но парсер LALR (N) может только смотреть на N символов, чтобы принять это решение. Yacc (и Byacc, Bison и т. Д.) Выполняют только LALR (1), поэтому они могут смотреть вперед только на один символ. Это оставляет несколько возможностей:

  1. полностью исключить возможность пустых списков
  2. Пусть лексер обрабатывает произвольное количество последовательных пустых списков как один токен
  3. использовать генератор синтаксического анализатора, который не ограничен грамматикой LALR (1)

Однако внутри грамматики yacc я не думаю, что вы можете многое сделать - ваша грамматика просто не соответствует ограничениям yacc.

1 голос
/ 21 марта 2011

С парсером снизу вверх, как правило, лучше избегать правильной рекурсии, как это показано в звездной строке грамматики ниже. 

list: LEFTBRACE RIGHTBRACE  
    | LEFTBRACE list RIGHTBRACE 
  **| num list**          
    | RIGHTBRACE

Вместо этого вы подумали о чем-то подобном?

value:value num
   | value string
   | value list
   | num
   | string
   | list

list: LEFTBRACE RIGHTBRACE
   | LEFTBRACE value RIGHTBRACE

Таким образом, у вас нет правильной рекурсии, а логика вложенности грамматики выражается проще.

...