Quale algoritmo utilizzare per analizzare le espressioni in questo semplice linguaggio?

Question

Quale algoritmo utilizzare per analizzare le espressioni in questo semplice linguaggio?

#1 da (1 voti)

0

Non voglio includere l'interezza della mia lingua, ma penso che la parte rilevante sia:

<expr> ::= <logical>
        |  <comparison>
        |  <constant>
        |  <addition>
        |  <subtraction>
        |  <multiplication>
        |  <division>

<logical> ::= <expr> "AND" <expr>
           |  <expr> "OR" <expr>
           |  "NOT" <expr>
           |  "(" <expr> ")"

<comparison> ::= <expr> "==" <expr>
              |  <expr> "!=" <expr>
              |  <expr> "<=" <expr>
              |  <expr> ">=" <expr>
              |  <expr> "<" <expr>
              |  <expr> ">" <expr>

Quello che sto cercando di fare è trasformare un codice che assomiglia a:

IF @var + 2 == 4 THEN
    something will happen
ELSE
    something else will happen
ENDIF

E trasformalo in un albero di sintassi. Il motivo per cui vorrei un albero di sintassi è che questo è il codice che deve essere eseguito in un interprete e potrebbe essere necessario eseguire più volte il programma (e @var può essere ogni volta diverso). La parte più difficile per me finora è che non si tratta di un vero interprete, il codice in realtà sta esprimendo una storia interattiva, qualcosa come Twine.

Ho iniziato a scrivere il parser e tutto sta andando bene fino a quando non ho raggiunto il punto delle espressioni. Ho scritto un algoritmo di smistamento prima di produrre Reverse Polish Notation, e credo di essere riuscito ad avere l'algoritmo dello shunting yard per produrre un albero di sintassi (facendo scattare e spingere i nodi sullo stack di uscita invece di solo numeri e operatori) ; ma non capisco davvero come incorporare gli operatori booleani / logici.

Esiste un algoritmo in grado di gestire sia espressioni matematiche come 1 + 2 sia le mie espressioni AND e == ?

Devo ripensare la mia sintassi sopra?

parsing

posta NeomerArcana 06.07.2018 - 13:37

fonte

1 risposta

Leggi altre domande sui tag parsing

Che cos'è federato, autenticazione certificata? Annotazione per definire i valori per l'argomento del metodo

score 1 · Answer 1

Allo stato attuale, la grammatica che hai specificato è una grammatica ambigua . Ad esempio qualcosa di

a AND b OR c

potrebbe avere due alberi di analisi, a seconda della modalità di parentesi.

Il ruolo dell'algoritmo Shunting-yard è di rimuovere questa ambiguità. Se si specifica la precedenza dell'operatore, viene fornita una parentesi univoca per la propria espressione. Quindi sì, mentre ti dà un AST per la tua espressione, non è davvero pensato per l'analisi.

Perché dico questo perché se si dispone di un albero di analisi corretto, allora ogni nodo avrebbe un non terminale associato (cioè <logical> , <comparison> , ecc.). Considerando che lo Shunting-yard, in sostanza, considera ogni espressione dello stesso tipo.

Quindi, se dovessi usarlo, riconoscerebbe questa grammatica:

<expr> ::= <expr> "AND" <expr>
        |  <expr> "OR" <expr>
        |  "NOT" <expr>
        |  <expr> "==" <expr>
        |  <expr> "!=" <expr>
        |  <expr> "<=" <expr>
        |  <expr> ">=" <expr>
        |  <expr> "<" <expr>
        |  <expr> ">" <expr>
        |  "(" <expr> ")"    
        |  <constant>
        |  <addition>
        |  <subtraction>
        |  <multiplication>
        |  <division>

Ma il fatto è che non si fa una distinzione tra espressione che valuta un valore numerico rispetto a espressioni che valutano un valore booleano nelle proprie produzioni. Tuttavia, stai utilizzando diversi non terminali per espressioni logiche e altre espressioni.

Vale a dire, la tua grammatica - nella sua forma attuale - accetta ( 1 + 2 ) AND @x e ( 1 == 2) >= 3 come validi.

Quindi potresti anche definire la tua grammatica come la grammatica di cui sopra. E poi puoi incorporarlo nell'algoritmo Shunting-yard come suggerito da amon nei commenti - assegnando la precedenza agli operatori logici e relazionali.

Potresti usare Precedenza dell'operatore C ++ come riferimento quando assegni la precedenza agli operatori logici e relazionali.