A Simple Syntax-Directed Translator

For example:

$list \rightarrow list + digit\ \ \ \ \ \ (1)$ $list \rightarrow list - digit\ \ \ \ \ \ (2)$ $list \rightarrow digit\ \ \ \ \ \ (3)$ $digit \rightarrow 0|1|2|3|4|5|6|7|8|9\ \ \ \ \ \ (4)$

The 10 productions for the nonterminal digit ( as you know, production (4) can be splited into 10 productions of the form like $digit \rightarrow 0$ ) allow it to stand for any of the terminals 0, 1, 2, …, 9. From production (3), a single digit by itself is a list. So, we can deduce 9-5+2 is a list as follows:

9 is a list by production (3)
9-5 is a list by production (2)
9-5+2 is a list by production (1)

Parsing is the problem of taking a string of terminals and figuring out how to derive it from the start symbol of the grammar.

A parse tree:

if nonterminal A has a production $A \rightarrow XYZ$, then a parse tree may have an interior node labeled A with three children labeled X, Y, and Z, from left to right.

Formally, given a context-free grammar, a parse tree according to the grammar is a tree with the following properties:

The root is labeled by the start symbol.
Each leaf is labeled by a terminal or by $\epsilon$.
Each interior node is labeled by a nonterminal.
If A is the nonterminal labeling some interior node and X1, X2, …, Xn are the labels 🏷 of the children of that node from left to right, then there must be a production $A \rightarrow X1X2…Xn$.

文法：它描述语言语法结构的一组形式规则。

文法的形式化定义：G = (VT, VN, P, S) VT: 终结符集合 VN: 非终结符集合 P: 产生式集合 S: 开始符号

上下文无关文法：它定义的语法范畴（或语法单位）是完全独立于这种范畴可能出现的环境。例如，在程序设计语言中，当碰到一个算术表达式时，我们完全可以“就事论事”处理，而不必考虑它所处的上下文。然而，在自然语言中，随便一个词，甚至一个字的意思在不同的上下文中都有可能有不同的意思。幸运的是，当今的程序设计语言都是上下文无关的。

这个文法最终要定义<句子>语法结构，所以<句子>在这里称为开始符号；<谓语>→<动词>这种书写形式称之为产生式。

终结符不能再进行推导。不是终结符的都是非终结符。非终结符可理解为一个可拆分元素，而终结符是不可拆分的最小元素。

空串ε既不属于终结符，也不属于非终结符。但是对于句子和句型的定义，可以将终结符和空串看成一个整体。因为句子是不包含非终结符的句型，句型可以包含非终结符、终结符和空串，因此句子可以包含终结符和空串。