Abstract syntax tree: Difference between revisions

Revision as of 20:13, 1 December 2021

Revision as of 16:12, 7 December 2021

Line 28:

* An AST usually contains extra information about the program, due to the consecutive stages of analysis by the compiler. For example, it may store the position of each element in the source code, allowing the compiler to print useful error messages.

ASTs are needed because of the inherent nature of programming languages and their documentation. Languages are often ambiguous by nature. In order to avoid this ambiguity, programming languages are often specified as a [[context-free grammar]] (CFG). However, there are often aspects of programming languages that a CFG can't express, but are part of the language and are documented in its specification. These are details that require a context to determine their validity and behaviour. For example, if a language allows new types to be declared, a CFG cannot predict the names of such types nor the way in which they should be used. Even if a language has a predefined set of types, enforcing proper usage usually requires some context. Another example is [[duck typing]], where the type of an element can change depending on context. [[Operator overloading]] is yet another case where correct usage and final function are determined based on the context. Java provides an excellent example, where the '+' operator is both numerical addition and concatenation of strings-dependent.

Although there are other [[data structure]]s involved in the inner workings of a compiler, the AST performs a unique function. During the first stage, the [[syntax analysis]] stage, a compiler produces a parse tree. This parse tree can be used to perform almost all functions of a compiler by means of syntax-directed translation. Although this method can lead to a more efficient compiler, it goes against the software engineering principles of writing and maintaining programs{{Citation needed|date=April 2015}}. Another advantage that the AST has over a parse tree is the size, particularly the smaller height of the AST and the smaller number of elements.

=== Design ===