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

Question

Чтобы предисловие к этому, мои знания о подобных вещах невелики.

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

Для справки, вот грамматику я написал (где S является начальным символом) в КНФ:

S -> х
А -> OS
S -> LB
B -> SR
S -> KS
О -> +
О -> -
О -> *
О ->/
О ->^
K -> -
L -> (
R ->)

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

Answer 1

Это похоже на проблему, связанную с конечным числом состояний автоматов, и я не помню все, что от моего курсовую, но я написал 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 и продолжить его веселый путь.

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

Answer 2

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

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

S -> EXPR 
EXPR -> (EXPR) 
EXPR -> - EXPR 
EXPR -> EXPR + EXPR 
EXPR -> EXPR - EXPR 
// etc... 

Answer 3

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

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 и т.д., так что вещи могут прекратить.

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