S2J's Studio.

编译原理

字数统计: 1.4k阅读时长: 4 min
2019/06/01 Share

大作业专栏

前言

杂谈

    编译原理也叫龙书,讲实话刚拿到这本书的时候,还觉得有点酷炫,因为看起来像一本魔法书,然后听老师一说挂科率,瞬间不敢轻视,挂科率和离散数学、数字电路一样多。然后各种句型、句柄、文法、llR、SLR等等名词概念洗刷着我堵塞的大脑,上课打一个瞌睡就忽然听不懂了。得课后疯狂看别人的博客去补,所以当老师布置编译原理的实践作业的时候,我超级害怕,担心完不成,因为我以为老师会让我们去写一个语言的编译器,可以说是还没看到题目就害怕了,然后得知题目的我释然了。

题目

熟悉 LEX 基本语法,掌握 Parser Generator 软件的使用;通过设
计、开发通用高级语言一个单词种类的词法分析程序,加深对课堂教
学内容(包括正规文法、正规表达式、有限自动机、NFA 到 DFA 的
转换、DFA 的最小化)的理解,提高词法分析方法的实践能力。

看起来很是艰涩难懂,夹杂各种名词概念,正规文法啊、正则表达式啊、自动机啥的。但仔细分析一下,就是用Parser Generator的lex写一个能识别你输入的东西,所有有时候看到任务的时候不要自己吓自己,一步步分析题目。
lex我也没很具体去掌握,因为老师只讲了一节课剩下的都是我课后看的。

LEX

想简单上手的话,可以把这lex分为几个部分,当用软件创建一个新的lex时会发现代码部分用几个%分割开来,而且满屏的备注

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
%{
//这里一般时自动生成的信息

%}

%name mylexer //你的lex的名字
{
// place any extra class members here
// 一般在这定义类似于java中的全局变量
}

// constructor
{
// place any extra initialisation code here
// 在这里初始化你的全局变量
}

// place any declarations here
chars [A-Za-z]
numbers ([0-9])+
//类似于上面的规定你的文法

%%

/////////////////////////////////////////////////////////////////////////////
// rules section

%{
// extract yylval for use later on in actions
myparser.YYSTYPE yylval = (myparser.YYSTYPE)yyparserref.yylvalref;
%}

// place your Lex rules here
{words} {yylval.strValue = new String(yytext,0,yyleng);
return myparser.WORDS;}
{numbers} {yylval.strValue = new String(yytext,0,yyleng);
yylval.value = Integer.parseInt(yylval.strValue);
return myparser.NUMBERS;}

//根据上面你写的文法去做出相应的动作,可以上面定义下面不做操作,但不能下面写了,而上面没有。
%%

/////////////////////////////////////////////////////////////////////////////
// programs section

}

看起来比较复杂且从没学习过的语言只是上手的话还是快的,我这里是基于java写的,所以就这个样子写出了我的编译原理实践作业,其他几项任务也类似的写完了。第二项还要用yacc

原理

只知道怎么操作却不知道原理,是很多大学生的通病,上手的话依样画葫芦还是简单的,可以把lex写的东西归纳为词法分析器,就像你拿到一句代码,先是一个词一个词看过去,标识符,关键词,操作符之类的,在你知道这些词代表的意思后,才能进行语法分析,所以电脑其实在模仿人脑,我觉得这句话其实也没错。语法分析使用yacc来写,分别判断推入和推出,就像x=3-2,这句话怎么得到,我们要先利用词法分析知道3和2属于数字,减号等号属于操作符,然后yacc负责决定当碰到一些词时进行的操作,先得到x,然后得到等号,得到等号后就会按照你的代码接着得到数字3,得到减号时触发你写的代码,电脑知道这个时候该去用3减掉2,再赋值给x。看起来很麻烦,但我们规定好代码后,电脑的速度可比我们快的多。

最近学习

最近学到了LR分析,LR 分析技术是功能最强的(自底向上)语法分析技术,适用文法广,效率高,分析能力强
不含移进规约冲突的是LR(0),然后便于理解LR是先一步步移进,发现可规约时便提前规约。

基本概念

拓广文法:增加产生式 S’→S,S’作为新的开始符号

在文法产生式右部的适当位置添加圆点构成项目

简单理解

在这里会碰到一个很好玩的东西·,这个东西有点像流水线工人一样做完一步往后移一步 A→XYZ
A→·XYZ A→X·YZ A→XY·Z A→XYZ·
小圆点一步步往后移,像上面的句子,当产生式接收到x时小圆点向后移,然后当小圆点后面是非终结符时,要写入文法中非终结符在左部的所有产生式,然后一步步往后推,直到小圆点到了最后面,利用这个小圆点就可以很轻松的画出lR分析的DFA,这大概是上了这么久编译原理以来最生动形象的吧。所以学习中碰到艰涩难懂的东西,把他形象化就会简单得多。

CATALOG
  1. 1. 大作业专栏
  2. 2. 前言