Formal Languages and Translators: Difference between revisions

From NovaOrdis Knowledge Base
Jump to navigation Jump to search
Line 44: Line 44:


==<span id='Syntax_Tree'></span>(Abstract) Syntax Tree==
==<span id='Syntax_Tree'></span>(Abstract) Syntax Tree==
The abstract syntax tree, also referred to as syntax tree, represents the hierarchical syntactic structure of the sentence.


==Parser==
==Parser==

Revision as of 21:20, 13 July 2018

Internal

Overview

Compiler

Interpreter

Lexical Analysis

Regular Expressions

Finite Automata

Syntax Analysis (Parsing)

TODO Deplete This Parsing

Grammar

Derivation. The leftmost derivation. The rightmost derivation.

Production

Production head

Production body

Terminal

Nonterminal


Backus-Naur Form (BNF)

Extended Backus-Naur Form (EBNF)

Parse Tree

A parse tree is a graphical representation of a derivation. Each interior node of a parse tree represents the application of a production and it is labeled with the name of the nonterminal that is the head of the production. The children node are labeled, from left to right, by the symbols in the body of the production. While is being constructed, the leaves of a parse tree may represent terminals and nonterminals, and at any moment, if they are read from left to right, they constitute the yield or the frontier of the tree, and it is also referred to as a sentential from of the grammar. A parse tree does not contain the information that reflects the order in which productions are applied to replace nonterminals. It is customary to produce parse trees by always producing the leftmost (or rightmost) derivation. Each parse tree has associated with it a unique leftmost and an unique rightmost derivation.

(Abstract) Syntax Tree

The abstract syntax tree, also referred to as syntax tree, represents the hierarchical syntactic structure of the sentence.

Parser

Top-Down Parser

Bottom-Up Parser

Semantic Analysis