Semantic Rules / Abstract Syntax Tree Rules

Question

First of all, are the Semantic Rules and Abstract Syntax Tree Rules the same?

Now, if i have a language specifications, and i have CFG, then how do i go about constructing Abstract Syntax Tree Rules. Any source is appreciated. Thanks.

Answer 1

"Abstract Syntax Tree" Rules (this is strange terminology) might be interpreted as those rules that shape the construction of the abstract syntax as parsing proceeds. These are usually written, in a grammar rule for a nonterminal T, as constructors over abstract syntax trees produced by parsing the subsidiary phrases of T. If

 T = '(' A ';' B ')' ;

is a grammar rule, an AST constructor for T might be

   T(A,B)

implying the construction of a T node with children being the ASTs constructed for the A and B subparses.

Semantic Rules are constraints that the program must meet to be legal, beyond the mere syntax. So one can construct an abstract syntax tree (from "rules"); doing so only demonstrates the program is syntactically correct. But the abstract syntax can say things that are simply nonsensical semantically, e.g.,

  "declare s as function; ...  s=7; ..."

The only way to check this in general is to walk over the abstract syntax tree, collecting facts locally (e.g., "s is a function" is a fact extracted from the declare statement; "s is assigned an integer" is collected from the assignment) and propagating those facts until the they meet and are shown to be (in)compatible.

Answer 2

To answer your second question, here's an article that ties together the concepts of a grammar and a syntax tree, and examines some parsing algorithms.

http://www.cs.purdue.edu/homes/xyzhang/spring11/notes/ast.pdf

From the article:

The resulting grammar is called the concrete grammar.  
The corresponding derivation tree is called the parse tree.

A concrete syntax tree or parse tree is a tree that represents the syntactic structure of a string according to some formal grammar.

Here is a link to an example derivation of a parse tree from a grammar:

http://www.cs.rochester.edu/~nelson/courses/csc_173/grammars/parsetrees.html

which also highlights the problem of dealing with ambiguous grammars.