【编译原理】02.导论---语法分析

发布于:2025-02-10 ⋅ 阅读:(14) ⋅ 点赞:(0)

在上一篇文章中,我们简单认识了编译以及词法分析,词法分析即将一条语句拆解成计算机可以理解的最小单元Token。

语法分析在编译器中的位置


我们可以看到语法分析器是位于词法分析器之后。
语法分析器的输入是:词法分析器输出的Token序列。
语法分析器输出是:语法树,它描述了代码的语法结构。

简单来说,即词法分析器负责把代码分解成基本单元,语法分析器则负责检查这些单元是否按照正确的顺序排列

语法分析

语法分析(Parsing)是检查代码是否符合语法规则的过程。

语法分析的核心任务:

  • 识别句法结构:从词法单元序列中识别出各种语言的结构(如表达式、语句、函数等)。
  • 构造语法树:将代码组织成层次化的树状结构,语法树的节点表示代码中的语法成分。

对比我们的中文句子,语法分析就是识别语言结构,然后构造语法树,来对句子的语法结构进行描述。

语法树

语法树(Parse Tree)是语法分析的核心输出,它是一种树状结构,表示代码的语法层次。
在语法树中:

  • 内部节点表示语法规则(如表达式、语句等)。
  • 叶子节点表示具体的词法单元(如标识符、数字、运算符等)。

语法分析的过程

语法分析依赖于语法规则,而语法规则通常由上下文无关文法(CFG)定义。
上下文无关文法由四部分组成:

  • 非终结符(Non-terminal symbols):表示语法结构的抽象概念,如 <表达式>、<语句>。
  • 终结符(Terminal symbols):实际的词法单元,如标识符(id)、运算符(+、*)、数字(60)。
  • 产生式规则(Production rules):定义非终结符如何展开成终结符和其他非终结符。
  • 起始符号(Start symbol):文法的入口,通常是 <程序> 或 <语句>。

语法分析的核心任务是将输入的词法单元序列按照语法规则组织成语法树。

下面我们来看两个例子。

position  =   initial  +   rate  *    60     ;

首先先对这个语句拆解成Token序列。
<id, position> <=> <id,initial> <+> <id, rate> <*> <num,60> <;>

  • = 是赋值操作的根节点。
  • 表达式 initial + rate * 60 被分解为多个子节点,展示运算符的优先级:*的优先级高于 +,所以 rate * 60 是一个独立的子树。

所以其语法树为:

int a , b , c ;

先看语句的Token序列。

  • int:关键字,表示整数类型,Token 为 <T, int>。

  • a:标识符,表示变量 a,Token 为 <IDN, a>。

  • ,:分隔符,表示逗号,Token 为 <COMMA, ->。

  • b:标识符,表示变量 b,Token 为 <IDN, b>。

  • ,:分隔符,表示逗号,Token 为 <COMMA, ->。

  • c:标识符,表示变量 c,Token 为 <IDN, c>。

  • ;:分隔符,表示语句结束,Token 为 <SEMI, ->。

根据文法规则,我们可以逐步构造语法树:

  • 根节点是 <D>,表示一个声明。
    - <D> 展开为 <T> <IDS>,以及终止符 ;
  • <T> 是 int,表示类型。
  • <IDS> 是一个标识符列表,由多个 id 和逗号组成。

所以其语法树为: