La ripetizione è espressa in forma Backus-Naur mediante definizioni di produzione ricorsiva?

0

Durante la lettura di grammatiche definite usando il modulo Backus-Naur (BNF), ho notato che le grammatiche non sembrano mai usare un simbolo di ripetizione esplicita, come * o + . Ciò è contrario alla forma Estendi Backus-Naur, tuttavia, che sembra avere simboli di ripetizione espliciti. L'articolo Wikipeida su EBNF menziona questo, in particolare nella sezione Convenzioni :

  1. The normal character representing each operator of Extended BNF and its implied precedence is (highest precedence at the top):'

    * repetition-symbol
    - except-symbol
    , concatenate-symbol
    | definition-separator-symbol
    = defining-symbol
    ; terminator-symbol
    . terminator-symbol
    

Sebbene abbia studiato prima il BNF, non ho mai veramente capito come BNF esprima molte delle funzionalità facilmente catturate in EBNF, in particolare la ripetizione.

Dopo aver osservato le grammatiche BNF più da vicino, credo che la ripetizione sia catturata usando definizioni ricorsive nelle produzioni. Ad esempio:

<number> ::= <digit> | <number> <digit>;
<digit> ::= 1 | 2 ... | 8 | 9;

Nella grammatica di cui sopra, un numero è definito come "una singola cifra o un numero seguito da una cifra", o in altre parole "una o più cifre". E mentre quanto sopra funziona bene per la ripetizione semplice, sembra essere più impegnativo esprimere modelli di ripetizione più complessi. Ad esempio, prendi la definizione di produzione file_input dalla grammatica di Python (3.6) :

file_input: (NEWLINE | stmt)* ENDMARKER

In che modo esattamente quanto sopra sarà tradotto in "classico" BNF (ignorando le differenze di sintassi)? Non sono sicuro di come sarebbe stato tradotto quanto sopra, pur conservando correttamente il significato espresso.

Le grammatiche BNF usano definizioni di produzione ricorsive per esprimere la ripetizione? In tal caso, come si comporta il metodo con esempi come quello sopra?

    
posta Christian Dean 28.08.2017 - 21:04
fonte

1 risposta

5

EBNF e BNF sono equivalenti; qualsiasi grammatica EBNF può essere convertita in una grammatica BNF.

Per il tuo esempio:

file_input: (NEWLINE | stmt)* ENDMARKER

file_input: <statements> ENDMARKER
<statements>: (<statements> (NEWLINE | stmt)) |
              empty

Ci sono alcune domande di overflow dello stack, ma ho trovato utile , in particolare il riassunto alla fine.

    
risposta data 28.08.2017 - 21:09
fonte

Leggi altre domande sui tag