某公司拟为某种新型可编程机器人开发相应的编译器。该编译过程包括词法分析、语法分析..

免费智能真题库 > 历年试卷 > 系统架构设计师 > 2016年下半年系统架构设计师上午试卷综合知识

第48题

知识点：管道／过滤器编译器词法分析集成开发环境开发环境语法分析语义分析

关键词：编译器词法分析代码生成机器人集成开发环境语法分析语义分析编译开发语义章/节：软件架构的风格

某公司拟为某种新型可编程机器人开发相应的编译器。该编译过程包括词法分析、语法分析、语义分析和代码生成四个阶段，每个阶段产生的结果作为下一个阶段的输入，且需独立存储。针对上述描述，该集成开发环境应采用（48）架构风格最为合适。

A. 管道-过滤器

B. 数据仓储

C. 主程序-子程序

D. 解释器

相关试题：经典软件架构风格

更多>

第51题 2010年下半年

62%

某公司欲开发一个漫步者机器人，用来完成火星探测任务。机器人的控制者首先定义探测任务和任务之间的时序依赖性，机器人接受任务..

第53题 2017年下半年

44%

系统中的构件和连接件都有一个顶部和一个底部，构件的顶部应连接到某连接件的底部，构件的底部则应连接到某连接的顶部，构件和构..

第50题 2018年下半年

61%

在仓库风格中，有两种不同的构件，其中，（49）说明当前状态，（50）在中央数据存储上执行。


知识点讲解
· 管道／过滤器 · 编译器 · 词法分析 · 集成开发环境 · 开发环境 · 语法分析 · 语义分析

管道／过滤器

在管道／过滤器风格中，每个构件都有一组输入和输出，构件读输入的数据流，经过内部处理，然后产生输出数据流。因此，这里的构件被称为过滤器，这种风格的连接件就像是数据流传输的管道，将一个过滤器的输出传到另一个过滤器的输入。此风格中特别重要的过滤器必须是独立的实体，它不能与其他的过滤器共享数据，而且一个过滤器不知道它上游和下游的标识。

一个典型的管道／过滤器架构的例子是以UNIX shell编写的程序。UNIX既提供一种符号，以连接各组成部分（UNIX的进程），又提供某种进程运行机制以实现管道。另一个著名的例子是传统的编译器。传统的编译器一直被认为是一种管道系统，在该系统中，一个阶段（包括词法分析、语法分析、语义分析和代码生成）的输出是另一个阶段的输入。

管道／过滤器风格的软件架构具有许多很好的特点：

（1）使得构件具有良好的隐蔽性和高内聚、低耦合的特点。

（2）允许设计者将整个系统的I/O行为看成是多个过滤器行为的简单合成。

（3）支持软件重用。只要提供适合在两个过滤器之间传送的数据，任何两个过滤器都可被连接起来。

（4）系统维护简单，可扩展性好。新的过滤器可以添加到现有系统中来；旧的可以被改进的过滤器替换掉。

（5）允许对一些属性，如吞吐量、死锁等进行分析。

（6）支持并行执行。每个过滤器是作为一个单独的任务完成，因此可与其他任务并行执行。

但是，这样的系统也存在着若干不利因素：

（1）通常导致进程成为批处理的结构。这是因为虽然过滤器可增量式地处理数据，但它们是独立的，所以设计者必须将每个过滤器看成一个完整的从输入到输出的转换。

（2）不适合处理交互的应用。当需要增量地显示改变时，这个问题尤为严重。

（3）因为在数据传输上没有通用的标准，每个过滤器都增加了解析和合成数据的工作，这样就导致了系统性能下降，并增加了编写过滤器的复杂性。

编译器

编译阶段要做的工作是用交叉编译或汇编工具处理源代码，产生目标文件。在嵌入式系统中，宿主机和目标机所采用的处理器芯片通常是不一样的。例如，目标机采用的CPU是DragonBall M68x系列或ARM系列，而宿主机采用的是x86系列。因此，为了把宿主机上编写的高级语言程序编译成可以在目标机上运行的二进制代码，就需要用到交叉编译器。

与普通PC中的C语言编译器不同，嵌入式系统中的C语言编译器要进行专门的优化，以提高编译效率。一般来说，优秀的嵌入式C编译器所生成的代码，其长度和执行时间仅比用汇编语言编写的代码长5%～20%。编译质量的不同，是区别嵌入式C编译器工具的重要指标。因此，硬件厂商往往会针对自己开发的处理器的特性来定制编译器，既提供对高级语言的支持，又能很好地对目标代码进行优化。

GNU C/C++（gcc）是目前比较常用的一种交叉编译器，它支持非常多的宿主机／目标机组合。宿主机可以是Unix、AIX、Solaris、Windows、Linux等操作系统，目标机可以是x86、Power PC、MIPS、SPARC、Motorola 68K等各种类型的处理器。

gcc是一个功能强大的工具集合，包含了预处理器、编译器、汇编器、连接器等组件。它在需要时会去调用这些组件来完成编译任务，而输入文件的类型和传递给gcc的参数决定了它将调用哪些组件。对于一般或初级的开发者，它可以提供简单的使用方式，即只给它提供C源码文件，它将完成预处理、编译、汇编、连接等所有工作，最后生成一个可执行文件。而对于中高级开发者，它提供了足够多的参数，可以让开发者全面控制代码的生成，这对于嵌入式系统软件开发来说是非常重要的。

gcc识别的文件类型主要包括：C语言文件、C++语言文件、预处理后的C文件、预处理后的C++文件、汇编语言文件、目标文件、静态链接库、动态链接库等。以C程序为例，gcc的编译过程主要分为4个阶段：

（1）预处理阶段，即完成宏定义和include文件展开等工作；

（2）根据编译参数进行不同程度的优化，编译成汇编代码；

（3）用汇编器把上一阶段生成的汇编码进一步生成目标代码；

（4）用连接器把上一阶段生成的目标代码、其他一些相关的系统目标代码以及系统的库函数连接起来，生成最终的可执行代码。

用户可以通过设定不同的编译参数，让gcc在编译的不同阶段停止下来，这样可以检查编译器在不同阶段的输出结果。

在gcc的高级用法上，一般希望通过使用编译器达到两个目的：检查出源程序的错误；生成速度快、代码量小的执行程序。这可以通过设置不同的参数来实现，例如，“-Wall”参数可以发现源程序中隐藏的错误；“-O2”参数可以优化程序的执行速度和代码大小；“-g”参数可以对执行程序进行调试。

词法分析

词法分析过程的本质是对构成源程序的字符串进行分析，是一种对象为字符串的运算。语言中具有独立含义的最小语法单位是符号（单词），如标识符、无符号常数与界限符等。词法分析的任务是把构成源程序的字符串转换成单词符号序列。

字母表、字符串、字符串集合及运算

（1）字母表∑：元素的非空有穷集合。例如，∑={a，b}。

（2）字符：字母表∑中的一个元素。例如，∑上的a或b。

（3）字符串：字母表∑中字符组成的有穷序列。例如，a、ab、aaa都是∑上的字符串。

（4）字符串的长度：字符串中的字符个数。例如，|aba|=3。

（5）空串ε：由0个字符组成的序列。例如，|ε|=0。

（6）连接：字符串S和T的连接是指将串T接续在串S之后，表示为S·T，连接符号“·”可省略。显然，对于字母表∑上的任意字符串S，S·ε=ε·S=S。

（7）空集：用符号Φ表示。

（8）∑*：指包括空串ε在内的∑上所有字符串的集合。例如，设∑={a，b}，∑*={ε，a，b，aa，bb，ab，ba，aaa，…｝。

（9）字符串的方幂：把字符串α自身连接n次得到的串，称为字符串α的n次方幂，记为αⁿ。α⁰=ε，αⁿ=ααⁿ^-1=αⁿ^-1α（n>0）。

（10）字符串集合的运算：设A、B代表字母表∑上的两个字符串集合。

.或（合并）：A∪B={α|α∈A或α∈B｝。

.积（连接）：AB=｛αβ|α∈A且β∈B｝。

.幂：Aⁿ=A·Aⁿ^-1=Aⁿ^-1·A（n>0），并规定A⁰={ε}。

.正则闭包+：A⁺=A¹∪A²∪A³∪…

.闭包*：A*=A⁰∪A⁺。显然，∑*=∑⁰∪∑¹∪∑²∪…

正规表达式和正规集

词法规则可用3型文法（正规文法）或正规表达式描述，它产生的集合是语言基本字符集∑（字母表）上的字符串的一个子集，称为正规集。

对于字母表∑，其上的正规式（正则表达式）及其表示的正规集可以递归定义如下。

（1）ε是一个正规式，它表示集合L（ε）={ε}。

（2）若a是∑上的字符，则a是一个正规式，它所表示的正规集为L（a）={a}。

（3）若正规式r和s分别表示正规集L（r）和L（s），则：

①r|s是正规式，表示集合L（r）∪L（s）。

②r·s是正规式，表示集合L（r）L（s）。

③r*是正规式，表示集合（L（r））*。

④（r）是正规式，表示集合L（r）。

仅由有限次地使用上述三个步骤定义的表达式才是∑上的正规式。

运算符“|”“·”“*”分别称为“或”“连接”和“闭包”。在正规式的书写中，连接运算符“·”可省略。运算符的优先级从高到低顺序排列为“*”“·”“|”。

设∑={a，b}，在下表中列出了∑上的一些正规式和相应的正规集。

正规式和相应的正规集

若两个正规式表示的正规集相同，则认为二者等价。两个等价的正规式U和V记为U=V。例如，b（ab）*=（ba）*b，（a|b）*=（a*b*）*。

有限自动机

有限自动机是一种识别装置的抽象概念，它能准确地识别正规集。有限自动机分为两类：确定的有限自动机和不确定的有限自动机。

（1）确定的有限自动机（Deterministic Finite Automata，DFA）。一个确定的有限自动机是个五元组：（S，∑，f，s₀，Z），其中：

①S是一个有限集合，它的每个元素称为一个状态。

②∑是一个有穷字母表，它的每个元素称为一个输入字符。

③f是S×∑→S上的单值部分映像。f（A，a）=Q表示当前状态为A、输入为a时，将转换到下一状态Q。称Q为A的一个后继状态。

④s₀∈S，是唯一的一个开始状态。

⑤Z是非空的终止状态集合，

一个DFA可以用两种直观的方式表示：状态转换图和状态转换矩阵。状态转换图是一个有向图，简称为转换图。DFA中的每个状态对应转换图中的一个结点；DFA中的每个转换函数对应图中的一条有向弧，若转换函数为f（A，a）=Q，则该有向弧从结点A出发，进入结点Q，字符a是弧上的标记。

例如，DFAM1=（{s₀，s₁，s₂，s₃}，{a，b}，f，s₀，{s₃}），其中f为：

f（s₀，a）=s₁，f（s₀，b）=s₂，f（s₁，a）=s₃，f（s₁，b）=s₂，f（s₂，a）=s₁，f（s₂，b）=s₃，f（s₃，a）=s₃

与DFAM1对应的状态转换图如下图（a）所示，其中，状态s₃表示的结点是终态结点。状态转换矩阵可以用一个二维数组M表示，矩阵元素M[A，a]的行下标表示状态，列下标表示输入字符，M[A，a]的值是当前状态为A、输入字符为a时，应转换到的下一状态。与DFAM1对应的状态转换矩阵如下图（b）所示。在转换矩阵中，一般以第一行的行下标对应的状态作为初态，而终态则需要特别指出。

确定的有限自动机示意图

对于∑中的任何字符串ω，若存在一条从初态结点到某一终止状态结点的路径，且这条路径上所有弧的标记符连接成的字符串等于ω，则称ω可由DFAM识别（接受或读出）。若一个DFAM的初态结点同时又是终态结点，则空字ε可由该DFA识别（或接受）。DFAM所能识别的语言L（M）={ω|ω是从M的初态到终态的路径上的弧上标记所形成的串}。

例如，对于字符串"ababaa"，在上图（a）所示的状态转换图中，识别"ababaa"的路径是s₀→s₁→s₂→s₁→s₂→s₁→s₃。由于从初态结点s₀出发，存在到达终态结点s₃的路径，因此该DFA可识别串"ababaa"。而"abab"和"baab"都不能被该DFA接受。对于字符串“abab“，从初态结点s₀出发，经过路径s₀→s₁→s₂→s₁→s₂，当串结束时还没有到达终态结点s₃；而对于串"baab"，经过路径s₀→s₂→s₁→s₃，虽然能到达终态结点s₃，但串尚未结束又不存在与下一字符"b"相匹配的状态转换。

（2）不确定的有限自动机（Nondeterministic Finite Automata，NFA）。一个不确定的有限自动机也是一个五元组，它与确定有限自动机的区别如下。

①f是S×∑→2^s上的映像。对于S中的一个给定状态及输入符号，返回一个状态的集合。即当前状态的后继状态不一定是唯一确定的。

②有向弧上的标记可以是ε。

例如，已知有NFAN=（{s₀，s₁，s₂，s₃}，{a，b}，f，s₀，{s₃}），其中f为：

f（s₀，a）=s₀，f（s₀，a）=s₁，f（s₀，b）=s₀，f（s₁，b）=s₂，f（s₂，b）=s₃

与NFAM2对应的状态转换图和状态转换矩阵如下图所示。

NFA的状态转换图和转换矩阵

显然，DFA是NFA的特例。实际上，对于每个NFAM，都存在一个DFAN，且L（M）=L（N）。

词法分析器的任务是把构成源程序的字符流翻译成单词符号序列。手工构造词法分析器的方法是先用正规式描述语言规定的单词符号，然后构造相应有限自动机的状态转换图，最后依据状态转换图编写词法分析器（程序）。

集成开发环境

嵌入式软件开发环境起初主要由专门开发工具的公司提供，这些公司根据不同操作系统和不同处理器版本进行专门定制，如美国Microtec公司的交叉开发工具曾经被VRTX、pSOS等定制采用。随着用户对开发工具套件的需求增加，一些著名的操作系统供应商开始发展本系列操作系统产品的开发工具套件，如WindRiver公司的Tornado、微软的Windows CE嵌入式开发工具包等。

在国际上，嵌入式软件开发环境的另一支研发队伍是GNU。GNU在因特网上提供免费的相关研究和开发成果，成为自主开发嵌入式软件开发环境的重要资源。一些公司已在GNU软件的基础上，经过集成、优化和测试，推出更加成熟、稳定的商业化嵌入式软件开发环境。

随着嵌入式系统的发展，嵌入式软件开发环境越来越重要，它直接影响到嵌入式软件的开发效率和质量。目前的开发环境已向开放性、集成化、可视化和智能化的方向发展，将各种类型且功能强大的软件工具，如编辑器、编译器、连接器、调试器、版本管理、用户界面等，有机地集成在一个统一的集成开发环境（Integrated Development Environment，IDE）中。

Tornado

Tornado是WindRiver公司推出的一个集成开发环境。它由三个高度集成的部分组成：运行在宿主机和目标机上的交叉开发工具和实用程序；运行在目标机上的实时操作系统VxWorks；用来连接宿主机和目标机的各种通信介质，如以太网、串口、在线仿真器ICE或ROM仿真器等。

Tornado提供的交叉开发工具和实用工具主要有：源代码编辑工具、图形化的交叉调试工具、工程配置工具、集成仿真工具、诊断分析工具、C/C++编译工具、宿主机-目标机连接配置工具、目标机系统状态浏览工具、命令行执行工具、多语言浏览工具及图形化内核配置工具等。在Tornado中，宿主机上的工具与目标机之间的通信由目标服务器和目标代理共同完成。如下图所示，在形式上目标代理是VxWorks上的一个任务。调试命令通过宿主机上的目标服务器发送给目标代理。这些调试请求决定了目标代理应如何控制目标机上的其他任务。

Tornado环境中宿主机与目标机之间的关系

.图形化的交叉调试器CrossWind/WDB：支持任务级和系统级两种调试方式，支持混合源代码和汇编代码显示，支持多目标同时调试，具有良好的图形用户界面。

.工程配置工具Project：用于对VxWorks操作系统及其组件进行自动配置，进行依赖性分析和代码容量计算，自动生成Makefile文件。

.集成仿真工具VxSim：提供与真实目标机完全一致的调试和仿真运行环境。

.诊断分析工具WindView：一个图形化的动态诊断和分析工具，主要是向开发者提供在目标机上运行的应用程序的许多详细情况。

.C/C++编译工具：Tornado提供以下支持C语言和C++语言的工具和类库：Diab C/C++编译器、GNU C/C++编译器及iostreams类库。

.宿主机-目标机连接配置工具Launcher：位于Tornado环境的最上层，开发者可以通过它来设置开发环境。

.目标机系统状态浏览工具Browser：一个图形化工具，能随时提供目标系统的全面状态信息。

.命令行执行工具WindSh：一个功能强大的命令行解释器，可以直接解释、执行C语言表达式，调用目标机上的C函数及访问已在系统符号表中定义的变量。

.多语言浏览工具WindNavigator：浏览源程序代码，用图形化的方式显示函数调用关系，从而实现快速的代码定位。

.图形化内核配置工具WindConfig：通过WindConfig提供的图形向导，用户可以方便地配置VxWorks内核及其组件的参数。

Tornado的特点：

（1）友好的开发环境。Tornado可以运行在不同的系统中，支持UNIX、Windows NT、Windows 98/95等。

（2）适用于开发不同类型的目标机。针对不同的目标机，Tornado为开发者提供了一个一致的图形接口和人机界面。这样，当开发人员转向新的目标机时，不必再花费时间去学习或适应新的开发工具。事实上，Tornado的所有工具都驻留在开发平台上。

（3）工具齐备，具有丰富的交叉开发工具和实用工具。

（4）开放的、可扩展的开发环境。Tornado是一个完全开放的环境，开发人员或第三方厂商可以很容易地把自己的工具集成到Tornado框架下。

Windows CE应用程序开发工具

如下图所示，Windows CE应用程序开发工具包括：①Platform Builder；②eMbedded Visual Tools；③eMbedded Visual Basic；④eMbedded Visual C++。它们都是专门针对Windows CE操作系统的开发工具。

Windows CE应用程序开发工具

Microsoft Windows CE Platform Builder为开发商迅速创建一个嵌入式系统提供了全部相关工具。Platform Builder集成开发环境使开发者能够对新一代高度模块化的设计进行配置、创建与调试，以实现嵌入式系统的灵活性与可靠性，并与Windows和Web功能特性紧密结合。它的特点主要包括：

.通过使用改进的目标-宿主集成与连接特性来提高工作效率，节省嵌入式系统的创建时间。这些特性包括：集成化连接与下载、集成化目标控制、状态监视器、灵活的创建选择、简化操作系统配置等。

.通过使用先进的系统级调试功能来提高调试速度。Platform Builder的系统级调试器目前可为硬件辅助和系统级调试提供支持，从而大大扩展了调试功能的作用范围。具体包括：硬件辅助调试、源点级调试、新型的内核追踪器、远程系统信息、远程性能监视器、改进的调试器用户界面、调试区间等。

.提供了一个新型扩展模型，可以帮助开发商将各类特性集成到开发环境当中。包括：微处理器控制单元、嵌入式开发工具控制单元等。

Microsoft eMbedded Visual C++和eMbedded Visual Basic是开发下一代Windows CE通信、娱乐及信息访问等应用程序时的功能强大的工具。它们所提供的全面高速应用程序开发环境能够帮助开发者在各类不同设备上，迅速就相关的Windows CE应用程序进行创建、调试和部署，并且在不牺牲控制功能、性能表现及有关灵活性的前提下，提高Windows CE的开发效率。这两个产品的特点主要包括：

.开发工作效率比较高。这两个集成开发环境与传统的Windows应用开发环境非常相似，因此开发人员无需额外的培训即可熟练掌握它们的使用方法。而编程时的在线提示辅助功能（如语句完成、参数信息和语法错误检查等），能够大大提高程序员的工作效率。另外，通过创建可重复使用的ActiveX组件，可以将软件开发的复杂程度降至最低水平。

.开发过程与集成化调试得以简化。允许eMbedded Visual Tools在编译完成后，从移动设备或模拟器上的IDE中自动复制并启动相关的应用程序，从而实现应用程序的迅速测试和执行。在调试程序时，可以使用集成化调试器，当应用程序在Windows CE设备上（或模拟器内）运行的同时对其错误予以消除。另外，在测试时可以先在Windows CE设备模拟器上对应用程序进行测试，以避免高昂的硬件成本投资。

.针对Windows CE平台的全面访问。包括TCP/IP通信机制、COM组件模型、ActiveX控件、设备的API接口函数等。

.面向最新的Windows CE设备创建相应的解决方案。例如，Handheld PC Pro、Palm-size PC及Pocket PC等Windows CE设备。

.迅速、灵活的数据访问。数据存储可通过相关连接来实现与远程数据源之间的同步。

Linux环境下的集成开发环境

在Linux环境下也有一些很好的集成开发环境，如Kdevelop、Eclipse和Anjuta等。

Kdevelop

Kdevelop是KDE小组开发的Linux/UNIX操作系统上的C/C++集成开发环境，为快速开发C/C++应用程序提供了强有力的开发工具。

Kdevelop的操作界面类似于微软的Visual Studio，提供编辑、编译、连接、除错、版本管理及计划管理等基本的IDE功能。此外它还内建了一个可以产生Qt图形界面的资源编辑程序。对于C++程序，它额外提供了类浏览器。此外其文件管理程序内建了所有有关KDE发展所需的文件，并提供搜寻的功能。

Eclipse

Eclipse是替代IBM Visual Age for Java（简称IVJ）的下一代IDE开发环境，但它未来的目标不仅仅是成为专门开发Java程序的IDE环境。根据Eclipse的体系结构，通过开发插件，它能扩展到任何语言的开发，甚至能成为图片绘制的工具。目前，Eclipse已经开始提供C语言开发的功能插件。而且它是一个开放源代码的项目，任何人都可以下载其源代码，并在此基础上开发自己的功能插件。

Anjuta

Anjuta是GNU/Linux平台下的C/C++集成开发环境，它主要是为了开发GTK/GNOME程序而设计的。Anjuta利用GLADE来生成优美的用户界面，加之以自己强大的源程序编辑功能，使之成为应用程序快速开发的集成开发环境。以前，人们使用GLADE做界面，用emacs或vi来编辑源程序，再用某种终端模拟器编辑开发项目。而现在使用Anjuta，所有这些繁杂零散的任务都可以在一个统一的、集成的、自然而然的环境下完成。

开发环境

下图是一个典型的CPD环境，通常包含三个高度集成的部分：

（1）运行在宿主机和目标机上的强有力的交叉开发工具和实用程序。

（2）运行在目标机上的高性能、可裁剪的RTOS。

（3）连接宿主机和目标机的多种通信方式。例如，以太网、串口线、ICE（In-Circuit Emulator，在线仿真器）、ROM仿真器等。

宿主机提供的基本开发工具有交叉编译器、交叉链接器和源代码调试器等，作为目标机的嵌入式系统则可能提供一个动态装载器、链接装载器、监视器和一个调试代理等。在目标机和宿主机之间有一组连接，通过这组连接程序代码，映像从宿主机下载到目标机，这组连接同时也用来传输宿主机和目标机调试代理之间的信息。

典型交叉平台开发环境

目前，嵌入式系统中常用的目标文件格式是COFF（Common Object File Format）和ELF（Executable Linking Format）。另外，一些系统还需要有一些专门工具将上述格式转换成二进制代码格式才可使用。典型地，一个目标文件包含：

（1）关于目标文件的通用信息，如文件尺寸、启动地址、代码段和数据段等具体信息。

（2）机器体系结构特定的二进制指令和数据。

（3）符号表和重定位表。

（4）调试信息。

语法分析

语法分析的任务是根据语言的语法规则，分析单词串是否构成短语和句子，即是否为合法的表达式、语句和程序等基本语言结构，同时检查和处理程序中的语法错误。程序设计语言的绝大多数语法规则可以采用上下文无关文法进行描述。语法分析方法有多种，根据产生语法树的方向，可分为自底向上（或自下而上）和自顶向下（或自上而下）两类。

上下文无关文法

上下文无关文法属于乔姆斯基定义的2型文法，被广泛地用于表示各种程序设计语言的语法。对于上下文无关文法G［S］=（VN，VT，P，S），其产生式的形式都是A→β，其中A∈V_N，β∈（V_N∪V_T）^*。

若不加特别说明，下面用大写英文字母A、B、C等表示非终结符，小写英文字母a、b、c等表示终结符号，u、v、w等表示终结符号串，小写希腊字母α、β、γ、δ等表示终结符和非终结符构成的文法符号串。由于一个上下文无关文法的核心部分是其产生式集合，所以文法可以简写为其产生式集合的描述形式。

（1）规范推导（最右推导）。如果在推导的任何一步

其中α、β是句型），都是对α中最右边的非终结符进行替换，则称这种推导为最右推导。最右推导常称为规范推导。同理可定义最左推导。

（2）短语、直接短语和句柄。设αδβ是文法G的一个句型，即

，且满足

和

，则称δ是句型αδβ相对于非终结符A的短语。特别地，如果有

，则称δ是句型αδβ相对于产生式A→δ的直接短语。一个句型的最左直接短语称为该句型的句柄。

自顶向下语法分析方法

自顶向下分析法的基本思想是：对于给定的输入串ω，从文法的开始符号S出发进行最左推导，直到得到一个合法的句子或者发现一个非法结构。在推导的过程中试图用一切可能的方法，自上而下、从左到右地为输入串ω建立语法树。整个分析过程是一个试探的过程，是反复使用不同产生式谋求与输入序列匹配的过程。若输入串是给定文法的句子，则必能成功，反之必然出错。

文法中存在下述产生式时，自顶向下分析过程中会出现下面的问题：

（1）若文法中存在形如A→αβ｜αδ的产生式，即A产生式中有多于一个候选项的前缀相同（称为公共左因子，简称左因子），则可能导致分析过程中的回溯处理。

（2）若文法中存在形如A→Aα的产生式，由于采取了最左推导，可能会造成分析过程陷入死循环的情况，产生式的这种形式被称为左递归。

因此，需要对文法进行改造，消除其中的左递归，以避免分析陷入死循环；提取左因子，以避免回溯。

（3）递归下降分析法。递归下降分析法直接以子程序调用的方法模拟产生式产生语言的过程，其基本思想是：为每一个非终结符构造一个子程序，每个子程序的过程体按该产生式候选项分情况展开，遇到终结符即进行匹配，而遇到非终结符则调用相应的子程序。该分析法从调用文法开始符号的子程序开始，直到所有非终结符都展开为终结符并得到匹配为止。若分析过程可以达到这一步，则表明分析成功，否则表明输入串中有语法错误。递归下降分析法的优点是简单且易于构造，缺点是程序与文法直接相关，对文法的任何改变都需要在程序中进行相应的修改。

（4）预测分析法。预测分析法是另一种自顶向下的语法分析方法，其基本模型如下图所示。

预测分析模型示意图

预测分析法的核心是预测分析表，可以用一个二维数组M表示，其元素M［A，a］（A∈V_N，a∈V_T∪#）存放关于A的产生式，表明当遇到输入符号为a且用A进行推导时，所应采用的产生式；若M［A，a］为error，则表明推导时遇到了不该出现的符号，应进行出错处理。

例如，根据文法G［E］=｛E→TE'，E'→+TE'｜ε，T→FT'，T'→*FT'｜ε，F→（E）｜id｜｝的构造的预测分析表如下表所示。

预测分析表

预测分析法的工作过程是：初始时，将“#”和文法的开始符号依次压入栈中；在分析过程中，根据输入串中的当前输入符号a和当前的栈顶符号X进行处理。

若X=a='#'，则分析成功；若X='#'且a≠'#'，则出错。

若X∈V_T且X=a，则X退栈，并读入下一个符号a；若X∈V_T且X≠a，则出错。

若X∈V_N且M［X，a］='A→α'，则X退栈，α中的符号从右到左依次进栈（ε无须进栈）；若M［X，a］='error'，则调用出错程序进行处理。

自底向上语法分析方法

常用的自底向上分析方法也称移进-归约分析法，工作模型是下推自动机，如下图所示。其基本思想是对输入序列ω自左向右进行扫描，并将输入符号逐个移进一个栈中，边移进边分析，一旦栈顶符号串形成某个句型的可归约串（即句柄）时，就用某个产生式的左部非终结符来替代，这称为一步归约。重复这一过程，直至栈中只剩下文法的开始符号且输入串也被扫描完时为止，确认输入串ω是文法的句子，表明分析成功；否则，进行出错处理。

移进-归约分析模型

LR分析法是一种规范归约分析法。规范归约是规范推导（最右推导）的逆过程，下面举例说明规范归约的过程。

LR分析法根据当前分析栈中的符号串（通常以状态表示）和向右顺序查看输入串的k个（k≥0）符号，就可唯一确定分析器的动作是移进还是归约，以及用哪条产生式进行归约，因而也就能唯一地确定句柄。当k=1时，已能满足当前绝大多数高级语言编译程序的需求。常用的LR分析器有LR（0）、SLR（1）、LALR（1）和LR（1）。

一个LR分析器由如下三个部分组成：

（1）驱动器。或称驱动程序。对所有LR分析器，驱动程序都是相同的。

（2）分析表。不同的文法具有不同的分析表。同一文法采用不同的LR分析器时，分析表也不同。分析表又可分为动作表（ACTION）和状态转换表（GOTO）两个部分，它们都可用二维数组表示。

（3）分析栈。其包括文法符号栈和相应的状态栈。

分析器的动作由栈顶状态和当前输入符号决定（LR（0）分析器不需向前查看输入符号），LR分析器的模型如下图所示。

LR分析器模型示意图

其中SP为栈顶指针，S_i为状态，X_i为文法符号。ACTION［S_i，a］=S_j规定了栈顶状态为S_i且遇到输入符号a时应执行的动作。状态转换表GOTO［S_i，X］=S_j表示当状态栈顶为S_i且文法符号栈顶为X时应转向状态S_j。

LR分析器的工作过程以格局的变化来反映。格局的形式为（栈，剩余输入，动作）。分析是从某个初始格局开始的，经过一系列的格局变化，最终达到接受格局，表明分析成功；或者达到出错格局，表明发现一个语法错误。因此，开始格局的剩余输入应该是全部的输入序列，而接受格局中的剩余输入应该为空，任何其他格局或者出错格局中的剩余输入应该是全部输入序列的一个后缀。

在LR分析过程中，改变格局的动作有以下4种：

（1）移进（shift）。当ACTION［S_i，a］=S_j时，把a移进文法符号栈并转向状态S_j。

（2）归约（reduce）。当在文法符号栈顶形成句柄β时，把β归约为相应产生式A→β的非终结符A。若β的长度为r（即｜β｜=r），则弹出文法符号栈顶的r个符号，然后将A压入文法符号栈中。

（3）接受（accept）。当文法符号栈中只剩下文法的开始符号S，并且输入符号串已经结束时（当前输入符是“#”），分析成功。

（4）报错（error）。当输入串中出现不该有的文法符号时，就报错。

LR分析器的核心部分是分析表的构造，这里不再详述。

语义分析

语义分析阶段分析各语法结构的含义，检查源程序是否包含静态语义错误，并收集类型信息供后面的代码生成阶段使用。只有语法和语义都正确的源程序才能翻译成正确的目标代码。

语义分析的一个主要工作是进行类型分析和检查。程序语言中的一个数据类型一般包含两个方面的内容：类型的载体及其上的运算。例如，整除取余运算符只能对整型数据进行运算，若其运算对象中有浮点数就认为是一种类型不匹配的错误。

在确认源程序的语法和语义之后，就可对其进行翻译并给出源程序的内部表示。对于声明语句，需要记录所遇到的符号的信息，所以应进行符号表的填查工作。在下图所示的符号表中，每一行存放一个符号的信息。第一行存放标识符X的信息，其类型为real，为它分配的地址是0；第二行存放Y的信息，其类型是real，为它分配的地址是4。因此，在该语言中，为一个real型数据分配的存储空间是4个存储单元。对于可执行语句，则检查结构合理的表达式是否有意义。对id1:=id2+id3*60进行语义分析后的语法树如下图所示，其中增加了一个语义处理节点inttoreal，该运算用于将一个整型数转换为浮点数。

语义分析后的符号表和语法树示意图

题号导航 2016年下半年系统架构设计师上午试卷综合知识

本试卷我的完整做题情况



	第48题在手机中做本题