编译原理练习题

### 编译原理知识点解析 #### 一、PL/0语言文法的BNF表示及其解析 **1. 文法概述** PL/0语言是一种简单的教学编程语言，其文法结构通过巴科斯范式（BNF）表示，用于描述语言的语法结构。这种文法清晰地展示了程序的构成要素，包括常量、变量、过程、语句等，并规定了它们之间的组合规则。 **2. 关键概念** - **常量说明部分**：定义常量的区域，格式为`CONST <常量定义>{,<常量定义>};`，其中`<常量定义>`定义了一个常量名及其等于一个无符号整数。 - **变量说明部分**：声明变量的地方，格式为`VAR <标识符>{,<标识符>};`，标识符由字母或数字组成，但开头必须是字母。 - **过程说明部分**：包含过程头部和过程体，可以多次嵌套，格式为`<过程首部><分程度>; {<过程说明部分>}`，其中`<过程首部>`指定过程名称。 - **语句**：程序的主要执行单位，包括赋值、条件、循环、调用、读写等操作。 **3. 语法规则详解** - **标识符**与**无符号整数**：标识符由字母开头的字母或数字序列组成，无符号整数则由一系列数字组成。 - **表达式与运算符**：表达式由项和运算符组成，运算符包括加减乘除以及关系运算符。例如，`<表达式>→[+|-]<项>{<加减运算符><项>}`。 - **条件语句**与**循环语句**：条件语句如`if <条件> then <语句>`，循环语句如`while <条件> do <语句>`，均基于表达式的结果来决定流程。 - **读写语句**：用于输入输出操作，如`read(<标识符>{，<标识符>})`和`write(<标识符>{，<标识符>})`。 #### 二、词法分析程序GETSYM的设计与实现 **1. 功能概览** GETSYM程序负责读取源代码并识别出单词，包括关键字、标识符、常量等，同时处理运算符和界符。它通过设置三个全程量SYM、ID、NUM来存储单词的类别、标识符的值以及数的值。 **2. 实现步骤** - **过滤空格**：去除单词间不必要的空格。 - **识别关键字**：通过查关键字表，将关键字转换为其内部编码表示。 - **识别标识符**：将其分类为`IDENT`，标识符本身存储在ID中。 - **处理数字**：数字的类别为`NUMBER`，具体数值存储在NUM中。 - **识别运算符**：识别由两个字符组成的运算符，如`>=`、`<=`等。 - **打印源程序**：边读入字符边打印，便于调试和检查。 **3. GETSYM的内部机制** GETSYM中定义了读字符过程`GETCH`，用于处理由一个或多个字符组成的单词。 #### 三、语法分析程序BLOCK的构建 **1. 功能介绍** BLOCK函数用于处理PL/0语言的语法分析和代码生成，特别针对过程的说明部分进行处理，创建名字表并分配相对地址。 **2. 工作流程** - **说明部分的处理**：为每个过程的说明对象创建名字表，记录层次、属性和相对地址。 - **语句处理和代码生成**：逐句分析语句，如果语法正确则生成目标代码。遇到标识符引用时查询名字表。 **3. 名字表构造** - **常量与变量**：记录名称、类型和值。 - **过程**：记录名称、层次、地址信息，过程名的地址在生成目标代码后返填。 - **动态更新**：每个过程的相对起始位置设定初始值为3，随过程的嵌套深度增加。 以上是对编译原理中PL/0语言文法、词法分析程序GETSYM及语法分析程序BLOCK的关键知识点的详细解析，涵盖了从语法结构到词法分析再到语法分析的核心内容，为理解编译原理提供了基础。