Compiler

编译器总体步骤

token

 

token、symbol、symbol table and the symbols definitions in grammar

 

 

语法分析

Syntax Analysis

词法分析出一个token后传给语法分析器，语法分析器根据文法从开始符号进行推导（以开始符号进行推导的规则，也可以称作是一个产生式）。词法分析器对输入字符串进行扫描分析的时候，是

按照从左至右依次进行扫描，按照这种方式扫描出来的token依次传给语法分析器进行解析，那么后面的推导也就是最左（leftmost）推导。

 

语法分析的任务就是分析文法结构以及判定输入的字符串是否能够被文法识别。语法分析可以是自顶向下（Top-down）语法分析，也可以是自底向上（Bottom-up）语法分析。

 

语法分析程序被称为Syntax Analyzer。通常也叫Parser。

 

语法分析根据语言文法规则构造语法分析树（Parsing tree）。

 

翻译单元

翻译单元（translation unit，compilation unit）在C语言中，翻译单元定义为：

1、一个.c（通常）的源程序文件可以认为是一个翻译单元。

在C语言中，在一个.c（通常）的源程序文件内定义的变量是不能在外面其他.c（通常）的源程序文件中引用，除非通过extern将这个变量声明为可全局访问的变量。

2、语句块可以认为是一个翻译单元。

在语句块内定义的变量是不能在语句块外面引用。

 

在C语言标准中，称之为“translation unit”。

 

 

语法分析单元

计算机编程语言发展这么多年，虽然出现了各种各样的编程语言。从编程语言范畴来看，有面向过程编程语言，面向对象编程语言，函数式编程语言等，各种语言范畴之间会相差比较大，不过同一

种类型语言之间语法都大同小异。

 

在所有编程语言中，C语言是最简单的一种编程语言，语法简单。即使语法已经相当简单，但其文法规则也相当复杂。C语言针对语句、表达式、类型定义、函数定义、函数声明、变量定义、变量声

明有一整套语法规则，或者说文法规则。

 

在C语言中，一条语句后面跟一个分号（；）作为这条语句的结束。包括类型定义、函数声明、变量声明，后面都一个分号（；）作为结束。例外的情况是，复合语句、语句块通过大括号括起来的

多条语句，这些在语句块后面不会一个分号（；）作为复合语句、语句块的结束，外面括起来的大括号本身作为复合语句、语句块的开始和结束。

 

对于输入的待解析字符串，应该怎样选择一个文法规则来进行进一步的语法分析。

 

 

 

复合语句

{

  ...

}

复合语句就是语句块

 

if (i) 

{

  ... 

}

 

switch (i)

{

  ...

}

 

while (i)

{

  ...

}

 

for ( ; ; )

{

  ...

}

 

void func()

{

  ...

}

 

在定义语言文法规则时，是否可以考虑不将这种作为结束符号的分号（；）加入语言文法规则中。

 

表达式

 

 

 

 

运算

表示法

中缀表达式(Infix Notation)

前缀表达式(Prefix Notation)

后缀表达式(Postfix Notation或Polish Notation)

 

大多数编程语言都是采用的是中缀表达式。包括C语言。

a + 1 * n

 

运算符

最常见的就是数学领域中的加、减、乘、除运算符号。数学领域中定义了大量的数学符号，编程语言中通常只定义一些比较常用的运算符，比如还有取余、与、或、异或、左移、右移、逻辑右移等

，有时候也称操作符。

 

操作符在编程语言中还有一个叫法，被称为运算子或操作子（operator），它们都表示同一个概念。

 

操作符

 

N-元操作符

也称做N-目操作符

主要就是一元操作符、二元操作符、三元操作符。超过三元的操作符很少，四元操作符基本没见过。

 

语句

 

函数调用

 

定义

 

声明

 

文法

文法结构

可以通过文法分析数或者文法分析表

 

文件包含文法

 

INCLUDE ::= '#' 'include' INCLUDE_FILE

INCLUDE_FILE ::= ANGLE_BRACKETS_INCLUDE_FILE | DOUBLE_QUOTES_INCLUDE_FILE

ANGLE_BRACKETS_INCLUDE_FILE ::= '<' IDENTIFIER '>'

DOUBLE_QUOTES_INCLUDE_FILE ::= '"' IDENTIFIER '"'

 

文件包含文法分析树

 

                     （INCLUDE）

                     /    |    \

               ('#') ('include') (INCLUDE_FILE)

                                       |

                         (ANGLE_BRACKETS_INCLUDE_FILE)

                            /          |         \

                         ('<')   (IDENTIFIER)   ('>')

 

 

                     （INCLUDE）

                     /    |    \

               ('#') ('include') (INCLUDE_FILE)

                                       |

                         (DOUBLE_QUOTES_INCLUDE_FILE)

                            /          |         \

                         ('"')   (IDENTIFIER)   ('"')

 

文件包含文法分析表

————————————————————————————+———+—————————+———+———+———

                            | # | include | < | > | " 

————————————————————————————+———+—————————+———+———+———

INCLUDE                     | Y |         |   |   |

————————————————————————————+———+—————————+———+———+———

INCLUDE_FILE                |   |         | Y |   | Y

————————————————————————————+———+—————————+———+———+———

ANGLE_BRACKETS_INCLUDE_FILE |   |         | Y |   |

————————————————————————————+———+—————————+———+———+———

DOUBLE_QUOTES_INCLUDE_FILE  |   |         |   |   | Y

————————————————————————————+———+—————————+———+———+———

 

逗号表达式文法

COMMA_EXPRESSION ::= EXPRESSION COMMA_EXPRESSION_TAIL

COMMA_EXPRESSION_TAIL ::= NULL | , COMMA_EXPRESSION

逗号表达式文法分析树

                             （COMMA_EXPRESSION）

                                 /          \

                         (EXPRESSION)    (COMMA_EXPRESSION_TAIL)

                                                    |

                                                  (NULL)

 

                             （COMMA_EXPRESSION）<————————————————+

                                 /          \                     |

                         (EXPRESSION)    (COMMA_EXPRESSION_TAIL)  |

                                               /         \        |

                                          (',')          +————————+

 

逗号表达式文法分析表

——————————————————————+—————————————+———+——————

                      | EXPRESSION  | , | NULL 

——————————————————————+—————————————+———+——————

COMMA_EXPRESSION      | Y           |   |      

——————————————————————+—————————————+———+——————

COMMA_EXPRESSION_TAIL |             | Y | Y    

——————————————————————+—————————————+———+——————

 

括号（parenthesis）表达式

PARENTHESIS_EXPRESSION ::= ( COMMA_EXPRESSION )

 

 

                          （PARENTHESIS_EXPRESSION）

                           /          |           \

                     ('(')   （COMMA_EXPRESSION）  (')')

                                 /          \

                         (EXPRESSION)    (COMMA_EXPRESSION_TAIL)

                                                    |

                                                  (NULL)

 

 

                          （PARENTHESIS_EXPRESSION）

                           /          |           \

                      ('(')           |            (')')

                             （COMMA_EXPRESSION）<————————————————+

                                 /          \                     |

                         (EXPRESSION)    (COMMA_EXPRESSION_TAIL)  |

                                               /         \        |

                                          (',')          +————————+

 

语法分析

 

自顶向下（Top-down）语法分析

自顶向下（Top-down）语法分析是对输入的字符串进行最左（leftmost）推导，从根开始构造语法分析树（Parsing tree），按照先序的方式构造语法分析树（Parsing tree）的节点。

 

自顶向下（Top-down）语法分析技术

递归下降语法分析（recursive-descent parsing）。

 

我觉得翻译成递归向下（或者向下递归）语法分析更容易让人理解。

对输入的字符串进行最左（leftmost）推导，依次从根开始构造语法分析树（Parsing tree），按照先序的方式梯归构造语法分析树（Parsing tree）的节点，如果无法继续递归构造下去，也就是

无法继续推导，则回溯上一个节点选择下一个规则继续进行推倒，直到推倒完成，如果所有可选择规则都无法继续推导，会依次回溯到根节点，也就是无法对输入的字符串进行推导，则推导失败，

这其实应该报语法错误。

 

采用这种语法分析技术也成为递归下降分析法或者递归子程序法。这样的语法分析器也叫做递归下降解析器或递归下降语法分析器。

 

LL(1)语法分析

SEE LL(1)

 

自底向上（Bottom-up）语法分析

 

语法分析树

语法分析树（Parsing tree）

 

AST

抽象语法树

 

赋值

i = i + 1

                        Assignment_statement

           /     |     \

                     Identifier   =   Expression

         /           /   |   \

i     Expression + Expression

                                   |            |

                               Identifier    Constant

                                   |            |

  i            1

 

函数调用

sum(1, 2)

要调用的函数名后面跟一个parenthesized的表达式，表达式内列出传入的参数列表。

 

                            Call_statement

           /     |     \

                     Identifier   =   Expression

         /               |    

sum    Parenthesized_Expression

                              /     |     |     |     \

                  Left_Parenthesis  |   Comma   |  Right_Parenthesis

                         |     Expression | Expression     |

                         (         |      ,     |          )

Constant     Constant

                                   |            |

                                   1            2

 

i = sum(1, 2)

 

              Assignment_statement

                   /    |     \

           Identifier   =   Call_Expression

               |            /     |     \

               i     Identifier   =   Expression

         /               |    

sum    Parenthesized_Expression

                              /     |     |     |     \

                  Left_Parenthesis  |   Comma   |  Right_Parenthesis

                         |     Expression | Expression     |

                         (         |      ,     |          )

Constant     Constant

                                   |            |

                                   1            2

 

if (i) 

  i = i + 1

 

                   

                                  If_Statement

                                   /        \

             Conditional_Expression          Assignment_statement

       |                        /     |     \

            Parenthesized_Expression        Identifier = Expression

                /       |      \                |           /   |   \

  Left_Parenthesis Expression Right_Parenthesis i    Expression + Expression

         |              |             |                  |            |

         (         Identifier         )              Identifier    Constant

                        |                                |            |

                        i                                i            1

 

 

定义

 

struct option

{

  char *name;

  int argc;

 

  char *value;

  char *default_value;

};

 

                           Struct_Definition

                          /    |       |    \

                    Struct Identifier  |     Semicolon

                      |        |       |         |

                    struct   option    |         ;

                                  Struct_Body

                                 /     |     \

                       Left_Brace      |      Right_Brace 

                           |           |           |

                           {           |           }

                                  Member_List

                                /   |     |   \

                         Member  Member Member  Member

                        / |  | \   ..     ..      ..

         Char_Type Asterisk Identifier Semicolon

             |         |         |         |

            char       *        name       ;

 

 

 

 

 

 

语法分析器

bison

https://www.gnu.org/software/bison

 

C语言编译器

通过文法规则来定义或约定C语言的优先级（precedence）、关联性（associativity）、分组（grouping）、序列点（sequence points）、协议点（agreement points）、求值顺序（order of evaluation），和相互交错（interleaving），以及lvalue和rvalue的判定是挺困难的，尤其是lvalue的判定。目前还没有一个好的方法，后续还得继续研究。