Prima di tutto, le regole semantiche e le regole dell'albero della sintassi astratta sono le stesse?Regole semantiche/Regole dell'albero della sintassi astratta
Ora, se ho un linguaggio specifico e ho un CFG, come faccio a costruire regole sintattiche astratte dell'albero. Qualsiasi fonte è apprezzata. Grazie.
Le regole "Abstract Syntax Tree" (questa terminologia è strana) potrebbero essere interpretate come quelle regole che modellano la costruzione della sintassi astratta durante l'analisi. Questi sono di solito scritti, in una regola grammaticale per una T non terminale, come i costruttori oltre albero sintattico astratto prodotte analizzando le frasi controllate di T. Se
T = '(' A ';' B ')' ;
è una regola grammaticale, un costruttore di AST per T potrebbe essere
T(A,B)
che implica la costruzione di un nodo T con figli essendo gli AST costruiti per le sottounità A e B.
Le regole semantiche sono vincoli che il programma deve soddisfare per essere legale, oltre la semplice sintassi. Quindi si può costruire un albero sintattico astratto (da "regole"); così facendo dimostra solo che il programma è sintatticamente corretto. Ma la sintassi astratta può dire le cose che sono semplicemente senza senso semantico, per esempio,
"declare s as function; ... s=7; ..."
L'unico modo per controllare questo, in generale, è quello di camminare sopra l'albero di sintassi astratta, la raccolta di dati a livello locale (ad esempio, "s è una funzione "è un fatto estratto dall'istruzione dichiarare;" s è assegnato un intero "viene raccolto dall'assegnazione) e la propagazione di tali fatti fino a quando non si incontrano e si mostra che sono (in) compatibili.
Per rispondere alla seconda domanda, ecco un articolo che collega i concetti di una grammatica e un albero di sintassi ed esamina alcuni algoritmi di analisi.
http://www.cs.purdue.edu/homes/xyzhang/spring11/notes/ast.pdf
Dall'articolo:
The resulting grammar is called the concrete grammar.
The corresponding derivation tree is called the parse tree.
Un concreto albero di sintassi o parse albero è un albero che rappresenta la struttura sintattica di una stringa secondo alcuni grammatica formale.
Ecco un link ad un esempio derivazione di un albero di analisi da una grammatica:
http://www.cs.rochester.edu/~nelson/courses/csc_173/grammars/parsetrees.html
che evidenzia anche il problema di trattare con le grammatiche ambigue.