An Abstract Syntax Tree(AST) is an abstract representation of the parse tree, which consists of nodes only for defined productions and terminal symbols. The AST has been widely used as a compact representation of the parse tree. To improve the readability and writability of the Context Free Grammar (CFG), the right-hand sides of the production rules are extended to be regular expressions over the terminal and nonterminal symbols, and this extended representation is called an Extended Context Free Grammar (ECFG).
The problem considered in this thesis is how to express teh AST in ECFGs when an ECFG is transformed to a CFG. The AST in ECFGs is implemented in a practical LALR(1) parser generator. In this thesis, it is found that a shift-reduce conflict may occur in rewriting the production rules from an ECFG to a CFG. The conflict is re-examined in the LALR lookahead set computation formalisms, and the way of the removal of the above conflict is also provided.
