Problem rozwiązujący konflikt zmniejszający zmianę w mojej gramatyce

Question

Próbuję napisać mały analizator składni z Irony. Niestety dostaję "konflikt redukujący zmiany". Gramatyki nie są moją mocną stroną i muszę tylko wykonać tę jedną małą rzecz. Oto zmniejszona gramatyka, która produkuje błąd:

ExpressionTerm := "asd" 
LogicalExpression := 
    ExpressionTerm | 
    LogicalExpression "AND" LogicalExpression | 
    LogicalExpression "OR" LogicalExpression 

Co robi „shift zmniejszyć konflikt” oznacza i jak mogę go rozwiązać? Rozumiem, że to oznacza, że ​​moja gramatyka jest niejednoznaczna, ale nie mogę wykręcić logiki w wystarczającym stopniu, aby zobaczyć, jak.

Dodano: Aby wyjaśnić - "asd" to po prostu ciąg literalny "asd". Tak bym się spodziewał, że następujące wyrażenia są przetwarzane przez tę gramatykę:

asd 
asd AND asd 
asd AND asd OR asd 
asd OR asd AND asd OR asd 

Dodany 2: Zapomniałem powiedzieć, korzeń gramatyki jest LogicalExpression.

Dodano 3: Ahh, mam! Niejednoznaczność ponieważ jest wyrazem jak

asd AND asd OR asd 

można interpretować na dwa różne sposoby:

(asd AND asd) OR asd 
asd AND (asd OR asd) 

Ale jak mogę rozwiązać ten problem? OK, mogę ustawić jedno z AND i OR, aby były silniejsze niż inne (i tak postanowiłem). Ale teraz widzę, że błąd pojawia się, nawet jeśli jest tylko jeden operator. Innymi słowy, ta produkuje również ten sam błąd:

LogicalExpression := "asd" | LogicalExpression "OR" LogicalExpression 

w tym przypadku chcę to:

asd OR asd OR asd 

być przetwarzane do tego:

(asd OR asd) OR asd 

Jaki jest nie- niejednoznaczny sposób robienia tego?

Dodano 4: Gotowy!

LogicalExpression1 := LogicalExpression1 "OR" LogicalExpression2 | LogicalExpression2 
LogicalExpression2 := LogicalExpression2 "AND" LogicalExpression3 | LogicalExpression3 
LogicalExpression3 := "NOT" LogicalExpression4 | LogicalExpression4 
LogicalExpression4 := "asd" | "(" LogicalExpression1 ")" 

Analizuje wszystkie wyrażenia logiczne, z operatorem jako NIE-> ORAZ-> LUB. "asd" można zastąpić wyrażeniem przeznaczonym dla twoich warunków.

Answer 1

Twoja gramatyka jest niejednoznaczna, jeśli używasz tylko pojedynczej przewężki. Aby zilustrować, czym jest "asd"? Czy jest to ExpressionTerm lub dłuższy termin. To jest konflikt redukujący zmiany. Podejrzewam tu także konflikt redukujący-redukuj.

Większość generatorów LL (1)/LALR (1) zapewni sposób radzenia sobie z konfliktem zmniejszającym przesunięcie za pośrednictwem operatorów priorytetowych. Większość będzie również domyślnie ustawiać najdłuższą sekwencję w przypadku konfliktu redukcji zmiany, więc często można je zignorować (po pewnym zbadaniu). (W tym przypadku może być konieczne przesunięcie pojedynczego terminu na dół, aby zachowywał się poprawnie).

Answer 2

Shift-Redukuj konflikt oznacza, że ​​twoja gramatyka jest niejednoznaczna. Dzięki regule rekursywnej token "asd" może być interpretowany jako część ExpressionTerm lub LogicalExpression, a parser nie może zdecydować, który. Potrzebujesz dodatkowej reguły, aby zerwać remis.

Answer 3

Shift zmniejszyć konflikty są jednym z trudniejszych rzeczy, aby uzyskać swój mózg wokół, jeśli chodzi o parsery. Najprostszym sposobem, aby zilustrować ten konflikt jest w tym pseudo kod:

if (a) then 
    if (b) then 
    printf('a + b'); 
    else 
    print('this could be a + !b or !a'); 

Oświadczenie inny może wiązać się z pierwszym lub drugim, jeśli. W przypadku niejednoznacznych gramatyk zazwyczaj definiuje się wartość określającą liczbę oczekiwanych zmian-redukuje ostrzeżenia w swojej gramatyce.

Alternatywnie można użyć parsera LL (k) lub LL (*). Te typy analizatorów składni nie mają dwuznaczności przesunięcia/zmniejszenia. W zależności od aplikacji mogą być łatwiejsze lub trudniejsze niż analizator LALR (1).

Answer 4

gramatyka jest niejednoznaczna w LL(1) lub LALR(1) od asd Token może być podstawiony w ExpressionTerm a także LogicalExpression spłaszczyć reguł gramatycznych rozwiązać shift/zmniejszenia konfliktów