Derivazioni in BNF

Question

Derivazioni in BNF

#1 da (1 voti)

0

Ottengo come eseguire una derivazione di un BNF. I miei libri di testo fanno un buon lavoro di spiegazione (molto meglio delle note di lezioni online di molti professionisti, ecc.). Esempio di seguito le mie domande:

<program> => begin <stmt_list> end
<stmt_list> => <stmt>
                   | <stmt>; <stmt_list>
<stmt> => <var> = <expression>
<var> => A | B | C;
<exression> => <var> + <var>
                   |<var> - <var>
                   |<var>

Genera:

<proogam> => begin<stmt_list> end
      => begin<stmt>;<stmt_list> end
      => begin<var> = <expression>;<stmt_list>end
      => begin a = <expression>;<stmt_list>end
      => begin a =  <var> + <var>;<stmt_list>end
      => begin a = b + <var> ; <stmt_list>end
      => begin a = b + c ; <stmt_list> end
      => begin a = b + c; <var> = <expression>; <stmt_list>end
      => begin a = b + c; b  = <expression>; end
      => begin a = b + c; b = <var> + <var>;<stmt_list> end
      => begin a = b + c; b = c + <var>; <stmt_list> end
      => begin a = b + c; b = c + a; <stmt_list> end
      => begin a = b + c; b = c + a; <var> + <expression>
      => begin a = b + c; b = c + a; c = <expression>;
      => begin a = b + c; b = c + a; c = <var>;
      => begin a = b + c; b = c + a;  c = b;

Ho ricevuto il maggior numero di volte e conosco il vantaggio di BNF. Ma riguardo le derivazioni, perché le facciamo token per token quando è abbastanza ovvio quale sarebbe il codice risultante?

Inoltre, con derivazione BNF, quando viene utilizzato un OR nella sintassi come si traduce questo? Ad esempio:

<if_stmt>  if (<logic_expr>) <stmt>| 
                   if (<logic_expr>) <stmt> else <stmt>

programming-languages language-design

posta Andrew S 24.03.2014 - 02:49

fonte

1 risposta

Leggi altre domande sui tag programming-languages language-design

Che cosa potrebbe essere usato per ottenere dati dal server ad Android alla stessa velocità con cui raggiunge i server? Come gestire più credenziali del database su più progetti

score 1 · Accepted Answer

Perché la struttura risultante non sarà ovvia per un compilatore. Un compilatore si muoverà attraverso la grammatica, passo dopo passo, in modo sistematico. In pratica, ci sono delle tecniche che possono scorciatoia, ma se vogliamo ragionare formalmente e rigorosamente sulle grammatiche, vogliamo che siano tutte le più esplicite possibili.

Questo porta direttamente alla sintassi OR. If_stmt è if (<logic_expr>) <stmt> o if (<logic_expr>) <stmt> else <stmt> . Ciò significa che possiamo quindi annidare ifs all'interno di elses e così via. Altrimenti, sono due affermazioni completamente diverse e, come ho detto prima, vogliamo essere il più esplicito possibile con le grammatiche BNF. Le grammatiche per i computer devono essere non ambigue. Se lasciamo fuori dei passi o siamo incuranti di come organizziamo le nostre strutture grammaticali, possiamo concludere con grammatiche ambigue in breve tempo. Questo in-turn può portare a sostanziali errori del compilatore.

Esempio:

some_statment ::= statement_components
    | other_possible_configuration
    | another_possible_configuration
    | yet_another_configuration

Nell'esempio sopra, ogni pipe (propriamente Sheffer Stroke) funziona come una "guardia" che agisce in modo come una dichiarazione di un caso in un linguaggio di programmazione. Passi attraverso le opzioni fino a raggiungere quella che corrisponde e poi quella che viene selezionata (tecnicamente lo fai all'indietro durante l'analisi ma sto divagando).