Convert C-Grammatik zu LL (1)

Ich baue gerade einen Compiler für C-. Ich arbeite gerade an dem Parser, und aus irgendeinem Grund kann ich anscheinend nicht die Kollision der ersten Sätze (der Terminal-ID) aus der EXPRESSION-Produktion auflösen. Unten, ist eine Teilmenge der Grammatik, die ich jetzt habe, könnte mir jemand in die richtige Richtung zeigen, wie man die Kollision auflöst (oder in eine äquivalente LL (1) analysierbare Grammatik umwandelt).Convert C-Grammatik zu LL (1)

EXPRESSION -> id VAR eq EXPRESSION | SIMPLEEXPRESSION 

VAR -> lbracket EXPRESSION rbracket | empty 

SIMPLEEXPRESSION -> ADDITIVEEXPRESSION FADDITIVEEXPRESSION 

FADDITIVEEXPRESSION -> RELOP ADDITIVEEXPRESSION | empty 

RELOP -> ltoreq | lt | gt | gtoreq | doubleeq | noteq 

ADDITIVEEXPRESSION -> TERM ADDITIVEEXPRESSION1 

ADDITIVEEXPRESSION1 -> ADDOP TERM ADDITIVEEXPRESSION1 | empty 

ADDOP -> plus | minus 

TERM -> FACTOR TERM1 

TERM1 -> MULOP FACTOR TERM1 | empty 

MULOP -> times | divide 

FACTOR -> lparen EXPRESSION rparen | id FACTOR1 | num 

FACTOR1 -> a | b

Quelle

2016-10-04 jay

Versuchen Sie, so viel wie möglich zu löschen, so dass die Form Ihrer (Sub-) Grammatik erhalten bleibt und das Problem erhalten bleibt. (Erster Schritt, wirf den Rest der Grammatik weg und konzentriere dich auf das, was du uns gezeigt hast). Wenn Sie nichts anderes löschen können, ohne das Problem zu lösen, starren Sie an, was übrig ist; oft werden Sie in der Lage sein, die verbleibende Grammatik zu ändern, um das Problem zu vermeiden. Dann füge alles zurück. Wenn Sie es zu diesem Zeitpunkt nicht herausfinden können, zeigen Sie uns die abgespeckte Grammatik als Erweiterung Ihrer Frage und sagen Sie, was Sie für das Problem halten. Sie werden mehr Rat bekommen. –

C nicht selbst verleihen sehr gut auf LL (1) Parsing, so was Sie versuchen, hier zu tun könnte ziemlich schwierig zu erreichen sein, und für die volle Grammatik nicht einmal möglich sein kann.

Aber für das Problem auf der Hand, für die Top-Level-Produktion

EXPRESSION -> id VAR eq EXPRESSION | SIMPLEEXPRESSION

es ist leicht zu sehen, dass id der Beginn jeder Alternative sein kann, so dass eine LL (1) Parser nicht wissen, welche alternativen nehmen.

Eine Lösung für das unmittelbare Problem wäre es, die EXPRESSION Produktion in zwei Alternativen zu spalten, eine, die immer mit einem id Terminal beginnt, und eine, die nie tut:

EXPRESSION  -> EXPRESSION_id | EXPRESSION_non_id

Für die id Alternative, würden wir erfordern die id Terminal vorne und dann id -nur Versionen der Produktionen erstellen, die folgen:

EXPRESSION_id  -> id (VAR eq EXPRESSION | SIMPLEEXPRESSION_id)

Auch für t er id Seite nicht-, würden wir nicht id Versionen der Produktionen erstellen, die folgen:

EXPRESSION_non_id -> SIMPLEEXPRESSION_non_id

die erforderlichen Teilproduktionen, die Grammatik vervollständigen würde wie folgt aussehen:

SIMPLEEXPRESSION_id -> ADDITIVEEXPRESSION_id FADDITIVEEXPRESSION 
ADDITIVEEXPRESSION_id -> TERM_id ADDITIVEEXPRESSION1 
TERM_id -> FACTOR_id TERM1 
FACTOR_id -> FACTOR1 

SIMPLEEXPRESSION_non_id -> ADDITIVEEXPRESSION_non_id FADDITIVEEXPRESSION 
ADDITIVEEXPRESSION_non_id -> TERM_non_id ADDITIVEEXPRESSION1 
TERM_non_id -> FACTOR_non_id TERM1 
FACTOR_non_id -> lparen EXPRESSION rparen | num

Sie können Machen Sie ähnliche Transformationen für andere Konflikte, aber die resultierende Grammatik kann ziemlich unhandlich werden.

Quelle

2016-10-05 12:58:43

Convert C-Grammatik zu LL (1)

Antwort

Verwandte Themen