È possibile analizzare la grammatica con produzioni su più righe senza retrocedere?

Question

È possibile analizzare la grammatica con produzioni su più righe senza retrocedere?

#1 da (2 voti)

0

Sto giocando con la creazione di un parser in PHP per il mio gusto di BNF , per abbinare le stringhe alla grammatica in questa variante BNF. È ancora un lavoro in corso e soggetto a modifiche (potrei persino finire per passare al supporto ABNF o EBNF , invece della mia variante), ma sta procedendo abbastanza bene.

Ora, perdonami se configuro la nomenclatura qui, ma credo che ciò che ho creato finora possa essere chiamato un parser LL (1) (o forse sarebbe meglio chiamarlo un lexer), nel senso che valuta la fonte un personaggio alla volta, senza retrocedere.

Nella mia variante BNF una regola di produzione è terminata da una nuova riga. Ma una cosa, tra le altre cose, che una grammatica definita nella mia variante BNF non consente ancora, è di avere regole di produzione su più righe. Sicuramente non è una necessità, ma sarebbe un piacere avere, per migliorare la leggibilità delle regole grammaticali.

Tuttavia, sto lottando per trovare un modo per analizzare una regola del genere, senza tornare indietro. Credo che potrei decidere di avere, per esempio, un punto e virgola come carattere di chiusura per una regola di produzione. Ma solo per curiosità: dovrebbe, in linea di principio, essere in grado di disambiguare le linee nuove come se fossero parte di una regola o la fine di una regola, senza tornare indietro? O semplicemente non è possibile?

Per tua considerazione, ecco una piccola grammatica di esempio (non esaustiva) nella mia variante BNF:

<DIGIT>      ::= "0"-"9"
<ALPHAHI>    ::= "A"-"Z"
<ALPHALO>    ::= "a"-"z"
<ALPHA>      ::= <ALPHAHI> |
                 <ALPHALO>
<ALPHANUM>   ::= <ALPHA> |
                 <DIGIT>

grammar parsing production lexer

posta Decent Dabbler 20.02.2016 - 21:09

fonte

1 risposta

Leggi altre domande sui tag grammar parsing production lexer

contenitore IoC con attributo lifetime [chiuso] Esegui e annulla l'azione nella stessa pagina / diversa - C'è una differenza?

score 2 · Accepted Answer

A rigor di termini, l'unico modo per evitare qualsiasi backtracking mentre si supportano le istruzioni multi-linea è quello di avere un esplicito carattere "la nuova fine non è la fine di una regola", o avere un esplicito "questa è la fine di una regola "personaggio diverso da una nuova riga. Come hai detto, puoi terminare le regole con il punto e virgola. Ma si potrebbe anche dire che qualsiasi riga che termina con la barra verticale | significa "questa regola continua alla riga successiva", e per BNF che potrebbe non essere del tutto irragionevole. I makefile usano il carattere backslash esattamente in questo modo.

Una soluzione molto più semplice per il tuo problema immediato sarebbe assumere che ogni regola debba iniziare con < su una nuova riga, e viceversa, in modo che ogni riga che inizia con qualcos'altro debba essere una continuazione di una regola avviata in precedenza. Questo probabilmente implica ancora uno o due personaggi di backtracking, quindi se questo è abbastanza buono dipende dal motivo per cui si vuole evitare il backtracking in primo luogo. Ma questa regola mi sembra più intuitiva e flessibile della regola delle "barre verticali delle estremità"

Ovviamente, il modo più corretto per analizzare questo è assumere che tutte le regole devono iniziare con un singolo non-terminale e ::= , ma ciò implicherebbe sicuramente il backtracking ad ogni ::= .