Разбор списка с минимальными разделителями - PullRequest
Новая
       44

Разбор списка с минимальными разделителями

2 голосов
/ 18 декабря 2010

У меня есть язык с инструкциями 4 видов: s00, s01, s10, s11, где ведущий 1 означает начальное ключевое слово, завершающий 1 означает завершенный, и у меня есть разделитель ";".Я могу прекратить любое утверждение с помощью «;».Я хотел бы разобрать язык, разрешающий список утверждений, который позволяет минимально использовать «;».Парсер Dypgen - GLR +.

Пример: 

{ x=1 fun f(){} x=1; x=1 var x=1 var x=1; x=1 }

Возможно ли вообще это сделать?Если так, то как?Если нет, то почему?

Я полагаю, что это невозможно, главным образом потому, что я не могу придумать, как это сделать :) Однако это кажется контекстно-зависимым: правило заключается в том, что вы должны вставить ";»между A и B, если A не завершен, а B не инициирован, то же самое для B и C, что означает, что B используется дважды.

Однако, поскольку синтаксическим анализатором является GLR +, соблазнительно просто использовать 

(s00|s01|s10|s11}*

как правило, и если он пропускается, добавьте ";"(который является s11 no-op), чтобы устранить неоднозначность.Было бы лучше, если бы синтаксический анализатор сообщал об ошибке синтаксиса.Возможно, это можно сделать при объединении альтернативных производств.Реальная проблема заключается в том, что они перекрываются, а не объединяются: если это произойдет, анализ программы может взорваться.

1 Ответ

1 голос
/ 18 декабря 2010

У меня недавно была похожая проблема с фразами верхнего уровня, некоторые из них нуждались в конце ;; в предыдущей фразе, а другие (начинающиеся с ключевого слова, вводящего фразу) - нет. Я решил свою проблему, разделив синтаксическую категорию фраз на две части, и задав прекрасные правила для последовательностей фраз, выражающих это поведение. Но это привело к дублированию в разделенной грамматике.

В вашем случае это будет что-то вроде: 

sequence:
  | (s00 | s10) sequence_closed
  | (s01 | s11) sequence_open
  | ε

sequence_closed:
  | s10 sequence_closed
  | s11 sequence_open
  | ';' sequence_open
  | ε

sequence_open:
  | s00 sequence_closed
  | s01 sequence_open
  | ε

Это немного сложнее, если вы хотите разрешить лишние разделители (и вы, скорее всего, хотите), но это идея.

...