Это двусмысленная грамматика? Как я должен решить это? - PullRequest
Новая
       17

Это двусмысленная грамматика? Как я должен решить это?

5 голосов
/ 26 июня 2010

В предисловии мои знания такого рода вещей ничтожны.

В любом случае, я разработал неконтекстную грамматику для описания структуры алебраических выражений, чтобы я мог научить себя, как CYKалгоритм разбора работает.Я понимаю, как такая структура может работать только с инфиксными алгебраическими выражениями, но я не могу понять, как разработать грамматику, которая может обрабатывать как унарные, так и двоичные определения оператора "-".

Для справки, вотграмматика, которую я написал (где S - начальный символ) в CNF:

S -> xA -> ОСS -> LBB -> SRS -> KSO -> +O -> -O -> *O -> /O -> ^К -> -L -> (R ->)

Проблема в том, что как алгоритм разбора CYK может заранее знать, стоит ли выбирать между S -> KS и A -> OS, когда он встречает оператор "-"?Такая грамматика больше не зависит от контекста?И самое главное, поскольку языки программирования могут обрабатывать языки как с двоичным, так и с унарным знаком минус, как мне разумно это проанализировать?

Ответы [ 3 ]

5 голосов
/ 26 июня 2010

Это похоже на проблему, связанную с конечными автоматами, и я не помню все из своей курсовой работы, но я написал парсер CYK в OCaml, поэтому я пойду дальше и сделаю снимок:)

Если вы пытаетесь разобрать выражение, например, 3- -4, ваше правило S -> K S будет использовать -4, а затем ваше правило A -> O S будет поглощать - -4. В конечном итоге это сработает до самого верхнего S правила производства. Вы должны быть осторожны с используемой вами грамматикой, так как указанное вами производственное правило A не может быть достигнуто с S, и вы, вероятно, должны иметь какое-то правило S -> S O S.

Способ работы алгоритмов синтаксического анализа CYK заключается в возврате, а не в «знании заранее», которое вы упомянули в своем вопросе. Ваш алгоритм CYK должен выполнить синтаксический анализ -4 как правила S -> K S, а затем снова попытаться поглотить второе - с правилом S -> K S, поскольку это производственное правило допускает произвольно длинную цепочку унарных -. Но как только ваш алгоритм обнаружит, что он застрял с промежуточным анализом 3 S, он поймет, что у него нет рабочих символов, которые он может использовать для анализа этого. Как только он поймет, что его больше нельзя анализировать, он вернется назад и вместо этого попытается вместо этого проанализировать - как правило S -> O S и продолжить свой веселый путь.

Это означает, что ваша грамматика остается не зависящей от контекста, поскольку контекстно-зависимая грамматика означает, что у вас есть терминалы в левой части правил производства, так что вы хороши в этом отношении. НТН!

2 голосов
/ 26 июня 2010

Грамматика неоднозначна, и синтаксический анализатор не может решить, какой случай взять.

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

S -> EXPR
EXPR -> (EXPR)
EXPR -> - EXPR
EXPR -> EXPR + EXPR
EXPR -> EXPR - EXPR
// etc...
1 голос
/ 26 июня 2010

Грамматики, основанные на алгебраических выражениях, довольно сложно устранить.Вот несколько примеров проблем, которые необходимо решить:

a + b + c естественным образом создает два дерева разбора.Чтобы решить эту проблему, вам необходимо устранить неоднозначность ассоциативности +.Вы можете пожелать, чтобы стратегия синтаксического анализа слева направо позаботилась об этом за вас, но будьте осторожны: возведение в степень, вероятно, должно ассоциироваться справа налево.

a + b * c естественным образом создает два дерева разбора.Чтобы решить эту проблему, вам нужно иметь дело с приоритетом оператора.

неявное умножение (a + bc), если это разрешено, создает всевозможные кошмары, в основном при токенизации.

Унарное вычитание проблематично, как вы упоминаете.

Если мы хотим решить эти проблемы, но по-прежнему имеем грамматику быстрого анализа, специализированную для алгебры, один из подходов состоит в том, чтобы иметь различные «уровни» EXPR, по одному для каждого уровня связывания, требуемого уровнями приоритета.Например, 

TERM -> (S)
EXPO -> TERM ^ EXPO
PROD -> PROD * EXPO
PROD -> PROD / EXPO
PROD -> -PROD
SUM -> SUM + PROD
SUM -> SUM - PROD
S -> SUM

Для этого также необходимо разрешить «продвижение» типов: SUM -> PROD, PROD -> EXP, EXP -> TERM и т. Д., Чтобы все могло завершиться.

Надеюсь, это поможет!

...