编译器总结-程序员宅基地

技术标签：编译器

1.词法分析和语法分析的定义

（1）词法分析

1）输入：组成源程序的字符流

2）输出：将字符流组成词素，生成并输出一个词法单元序列。每个词法单元对应于一个词素。词法分析器返回词法单元名字和描述该词法单元的词素的属性值。词法单元的名字将影响语法分析过程的决定，而这个属性会影响语法分析之后的对这个词法单元的翻译。

3）关键术语：

a. 词素：源程序的一个字符序列，它和某个词法单元的模式匹配，并被词法分析器识别为该词法单元的一个实例。

b.模式：描述一个此法单元的词素可能具有的形式，当词法单元是一个关键字时，它的模式就是组成这个关键字的字符序列。对于标识符和其他词法单元，模式是一个更加复杂的结构，它可以和很多符号串匹配。正则表达式是用来描述词素模式的重要表示方法。

c.词法单元：由一个词法单元名和一个可选的属性组成。词法单元名是一个表示某种词法单位的抽象符号，比如一个特定的关键字，或者代表一个标识符的字符序列。词法单元名字是由语法分析器处理的输入符号。词法单元id（标识符）有关的信息：词素，类型，它的第一次出现的位置都保存在符号表中。一个标识符的属性值是一个指向该符号表中该标识符对应条目的指针。

示例：

每个关键字有一个词法单元；模式为其自身；

表示运算符的词法单元；

一个表示所有标识符的词法单元；

一个或多个表示常量的词法单元；

每一个标点符号有一个词法单元；

4）三大作用：

识别词素；过滤源程序中的注释和空白符；将编译器生成的错误消息与源程序的位置联系起来。

5）正则表达式与有穷自动机的关系：

正则表达式的规则很容易理解，但是正则表达式并不能直接用来解析字符串，我们还要引入一种适合转化为计算机程序的模型。

有穷自动机（finite automation，FA）,有时也叫有穷状态机（finite state machine）。有穷自动机首先包含一个有限状态的集合，还包含了从一个状态到另外一个状态的转换。有穷自动机看上去就像是一个有向图，其中状态是图的节点，而状态转换则是图的边。此外这些状态中还必须有一个初始状态和至少一个接受状态。下面的图展示了一个有穷自动机，有根从外边来的箭头指向的状态表示初始状态，有个黑圈的状态是接受状态：

现在我们来看看有穷自动机怎么处理输入的字符串：

一开始，自动机处于初始状态
输入字符串的第一个字符，这时自动机会查询当前状态上与输入字符相匹配的边，并沿这条边转换到下一个状态。
继续输入下一个字符，重复第二步，查询当前状态上的边并进行状态转换
当字符串全部输入后，如果自动机正好处于接受状态上，就说该自动机接受了这一字符串

一个自动机接受的所有字符串组成的集合称作这个自动机的语言。

上图的自动机是一个确定性有穷自动机（DFA），其特点是从每一个状态只能发出一条具有某个符号的边。也就是说不能出现同一个符号出现在同一状态发出的两条边上。但是，还有一种非确定性有穷自动机（NFA），它允许从一个状态发出多条具有相同符号的边，甚至允许发出标有ε（表示空）符号的边，也就是说，NFA可以不输入任何字符就自动沿ε边转换到下一个状态。下图展示了一个非确定性有穷自动机：

非确定性有穷自动机在遇到两条边上有相同的符号，会选择哪一边呢？遇到ε边到底会转移还是不会转移呢？答案是，NFA会自动猜测应该选择哪一条边，而且每次都能猜对。DFA、NFA和正则表达式是等价的，任何NFA都存在一个与之接受同样语言的DFA，和一个定义相同语言的正则表达式。这三种模型虽然定义迥然不同，但却表示同样的正则语言。

（2）语法分析

1）输入

词法单元序列（串）

2）输出

语法树。语法分析器的主要作用是是否可以以及如何从语法的起始符号推导出输入符号串（验证该词法单元序列是否可以由源语言的文法生成）。主要有自顶向下语法分析技术和自底向上的语法分析技术。这两种方法中，语法分析器的输入串总是按照从左至右的方式被扫描，每次被扫描一个符号。

3）自顶向下语法分析

可被看作是为输入串构造语法分析树的过程，它从语法分析树的根结点开始，按照先根次序（深度优先地）创建这棵语法分析树的各个结点。自顶向下语法分析可以被看作寻找输入串的最左推导的过程。

4）自底向上的语法分析

可被看作是为输入串构造语法分析树的过程，它从叶子结点（底部）开始逐渐向上到达根结点（顶部）。自顶向下语法分析可以被看作寻找输入串的最右推导的逆过程。移进-规约语法分析是自底向上语法分析的一种形式。

本文链接：https://blog.csdn.net/wz3118103/article/details/39323497

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

dh密钥协商算法c语言实现,Diffie-Hellman密钥协商算法-python实现-程序员宅基地

文章浏览阅读2.6k次。Boblee人工智能硕士毕业，擅长及爱好python，基于python研究人工智能、群体智能、区块链等技术，并使用python开发前后端、爬虫等。1.Diffie-Hellman密钥协商算法Diffie-Hellman密钥协商算法在1976年在Whitfield Diffie和Martin Hellman两人合著的论文New Directions in Cryptography(Section Ⅲ..._dh算法c语言

学计算机需要右脑还是左脑,学心理：你的左脑更强还是右脑更强？来测测你惯用哪侧大脑...-程序员宅基地

文章浏览阅读259次。学心理：你的左脑更强还是右脑更强？来测测你惯用哪侧大脑测试开始：1、你看到的猫，是在往哪个方向旋转呢？顺时针旋转1分逆时针旋转2分2、我们知道正方形是有角的图形，如果有一个图形没有角，那么可以肯定的是：这个图形是个圆1分这个图形不是正方形2分3、你在下图最先看到什么动物？白色的兔子1分黑色的猫2分4、有四个人坐在树上，如下图所示，你觉得他们谁最蠢？1号3分2号2分3号4分4号1分5、如下图所示，有..._学习编程哪边大脑好一些

Teradata自定义函数Replace-程序员宅基地

文章浏览阅读1.2k次。Teradata没有函数replace，为了方便使用，定义了一个。其实也挺简单的，描述如下：一、用c编写一个replace函数，挺简单，也可以在网上找到源码，编译通过，能达到目的即可。二、运行一个bteq，将自定义函数载入。详细..._terdata自定义函数

用java写一个完整的扑克牌游戏-程序员宅基地

文章浏览阅读269次。写一个完整的扑克牌游戏需要考虑以下几个方面：扑克牌类：这个类表示一张扑克牌，需要存储花色和数字。扑克牌组：这个类表示一副扑克牌，需要存储52张扑克牌，并提供洗牌，发牌等功能。玩家类：这个类表示一个玩家，需要存储该玩家的名字，手中的牌，得分等信息。游戏类：这个类是游戏的主要逻辑，负责记录每个玩家的信息，进行游戏的流程控制，判定输赢等。以上是一个简单的扑克牌游戏的类结构，如果需要..._java创建扑克牌

Anaconda安装配置pytorch环境及opencv安装_anaconda环境冲突-程序员宅基地

文章浏览阅读6.3k次，点赞4次，收藏44次。Anaconda安装配置pytorch环境及opencv安装1.安装说明本教程使用Anaconda建立Pytorch虚拟环境来安装Pytorch。2.为什么要使用Anaconda虚拟环境安装Pytorch？因为环境中通常需要安装很多软件，例如：我同时在使用tensorflow框架。但是他们所需要的Python的关联模块或版本会有所差异。如果都装在一个环境中难免会引起冲突。所以，选择虚拟环境能很好地避免环境之间的冲突。（一）pytorch环境搭建首先，在anaconda新建虚拟环境，然后在虚拟环境_anaconda环境冲突

ubuntu：安装cmake后查看版本报错：CMake Error: Could not find CMAKE_ROOT !!!_cmake has most likely not been installed correctly-程序员宅基地

文章浏览阅读2k次。问题描述：ubuntu18原来安装过cmake，想升级下版本，在安装新版本的cmake完成后，输入指令：cmake -version 查看版本号时出现以下错误：CMake Error: Could not find CMAKE_ROOT !!!CMake has most likely not been installed correctly.Modules directory not found in/usr/local/share/cmake-3.10cmake version 3.1_cmake has most likely not been installed correctly