Sto cercando di capire la differenza tra valori terminali e non terminali in un linguaggio reale. Non sono riuscito a trovare abbastanza esempi su CFG in linguaggio reale su Internet, la maggior parte degli esempi sono astratti. Supponiamo di avere il seguente
int main(){
int a = 5;
return a + 6;
}
Le seguenti affermazioni sono vere?
Terminali: int, (,), {,}, 5, return, +, 6,;
Non-terminali: principale, a
I simboli terminale e non terminale sono un aspetto di una grammatica , non di una lingua . In una grammatica BNF (che descrive un linguaggio senza contesto), i non terminali sono i simboli "a sinistra".
Ad esempio, potrebbe essere una semplice grammatica C-ish (usando i quantificatori di tipo regex BNF +):
<program> ::= <function>*
<function> ::= <type> <identifier> '(' ')' <block>
<block> ::= '{' <statement>* '}'
<statement> ::= <statement_define>
<statement> ::= <statement_return>
<statement_return> ::= 'return' <expr> ';'
<statement_define> ::= <type> <identifier> '=' <expr> ';'
<expr> ::= <expr> '+' <term>
<expr> ::= <term>
<term> ::= <identifier>
<term> ::= <literal>
Come definito, i simboli programma, funzione, blocco, istruzione, statement_return, statement_define, expr e term sono non-terminali. Possono essere sostituiti con il loro lato destro. Al contrario, i simboli type, identifier, (,), {,}, return,;, + e literal sono terminali perché non sono definiti nella grammatica. Formano "l'alfabeto" su cui questa grammatica funziona.
In pratica la grammatica di cui sopra è incompleta perché alcuni simboli non sono stati definiti, quindi un parser separato (chiamato tokenizer, scanner o lexer) sarebbe responsabile per riconoscerli.
Una grammatica può essere usata per descrivere la struttura di un dato input. Ad esempio, un tokenizer potrebbe trasformare il codice sorgente in un flusso di token
type:int, identifier:main, (, ), {,
type:int, identifier:a, =, literal:5, ;,
return, identifier:a, +, literal:6, ;,
}
che il parser si trasformerebbe in un albero di sintassi astratto basato sulla grammatica. Qui:
program
+ function
+ type: int
+ identifier: main
+ '('
+ ')'
+ block
+ '{'
+ statement
+ statement_define
+ type: int
+ identifier: a
+ '='
+ expr
+ term
+ literal: 5
+ ';'
+ statement_return
+ 'return'
+ expr
+ term
+ identifier: a
+ '+'
+ term
+ literal: 6
+ ';'
+ '}'
Possiamo anche usare la grammatica per generare il codice sorgente, sostituendo i simboli non terminali. Ad esempio:
<program>
<function>
<type> <identifier> ( ) <block>
<type> <identifier> ( ) { <statement>* }
<type> <identifier> ( ) { <statement_return> }
<type> <identifier> ( ) { return <expr>; }
<type> <identifier> ( ) { return <term>; }
<type> <identifier> ( ) { return <literal>; }
A quel punto non rimangono simboli non terminali (come definito dalla grammatica).
I simboli del terminale sono tutti i simboli che possono apparire direttamente nella lingua.
Nel tuo caso puoi osservare int , ( , ) , { , } , 5 , return , + , 6 , ; , = , main e a .
I simboli non terminali sono tutti i simboli intermedi usati nella definizione delle regole grammaticali, che saranno derivati ulteriormente fino alla completa sostituzione con i simboli del terminale. Sono costrutti grammaticali astratti della lingua.
Nel tuo caso, e usando la grammatica dell'appendice A di K & R, è: programma , definizione esterna , definizione della funzione, tipo -specificatore, funzione-dichiaratore, corpo-funzione, dichiaratore, elenco-parametri, identificatore, tipo-decl-elenco, istruzione-funzione, lista-dichiarazione, lista-istruzioni, istruzione, dichiarazione, inizializzatore, espressione, valore, primario, costante , binop, e * asgnop (penso di averne perso qualcuno, ma spero che tu abbia la logica).
Una grammatica , è una grammatica in cui tutte le regole di produzione hanno la forma X -> Y dove X è un non-terminale, e Y è un gruppo non vuoto di terminali e non terminali.
Leggi altre domande sui tag programming-languages c grammar compiler parsing