编译原理实验教案计算机专业教研室季玉茹实验一：词法分析程序设计实验目的1．巩固对词法分析的基本功能和原理的认识。
2．能够应用自动机的知识进行词法分析。
3．理解并处理词法分析中的异常和错误。
实验要求1．掌握词法分析的基本功能，并将其实现。
2．词法分析程序应具有较好的可扩展性，应清晰明确。
3．除对相关问题的全面考虑外，还需对局部作一些优化考虑（如符号表）。
3．明确词法分析的基本功能和原理。
4．在词法分析中哪些地方体现自动机意识。
5．词法分析的异常和错误处理。
6．编写并运行该题目程序代码，具有该题目的参考答案。
7．深刻理解题目内涵，能够清晰描述问题，掌握该题目涉及的知识点，指导学生实验时需要注意的问题。
实验原理参考教材第2章2.3节和下图算法，可以做Pascal语言的词法分析程序；单词的种类分为五种：1．Pascal常用保留字：AND,ARRAY,BEGIN,CASE,CONST,DIV,DO,DOWNTO,ELSE,END,FILE,FOR,GOTO,FUNCTION,IF,IN,LABEL,MOD,NOT,OF,OR,PACKEN,PROCEDURE,PROG RAM,RECORD,REPEAR,SET,THEN,TO,TYPE,UNTIL,V AR,WHILE,WITH2.标识符：[字母]{字母|数字}另外标识符里包括：标准常量：false,ture标准类型：integer,boolen,real,char,text标准文件：input,output标准过程：read,readln,write,writeln3.运算符：+，-，*，/，DIV，MOD，OR，AND，NOT，<,<=,=,>=,>,<>,:=4.界符：“，”，“.”,“、”，“（”，“）”，“：”，“；”5.常数：如10，25，100，14.25实验内容对一段类高级语言代码进行词法分析，并输出词法分析的结果。
四、使用算法1、模块4：识别标识符输入：CH中含标识符的首字母；输出：TOKEN(二元式形式)；procedure RECOGID(CH，TOKEN)；beginWORD:=''；／*WORD存放标识符*／WORD:=WORD||CH；／*||表示连接*／repeatcall GETCH(CH)；／*读下一字符*／if CH是字母或数字then WORD：＝WORD||CH；until CH!=字母或数字；if CH是非法字符then call PRINTERR('非法字符')else 列计数-1；／*不是非法字符时列计数-1*／if WORD是关键字then TOKEN:=(关键字种别码,_)else begin／*查填符号表，ENTRY为标识符在表中的入口*／call LOOKUP(WORD，'标识符'，ENTRY)；TOKEN:=(标识符种别码，ENTRY)end；returnend；对于识别较为复杂单词的模块，可以先画出该单词的状态转换图或语法图，然后再根据状态图给出模块详细说明。
2、模块6：处理注解(HANDLECOM)；输入：'/'；进入该模块之前已扫描了一个符号'/'输出：'/'的TOKEN字或空TOKEN宇；procedure HANDLECOM(TOKEN)；begin call GETCH(CH)；if CH!='*'then ／*'/'表示除号*／begin 列计数-1；TOKEN＝('/'的种别码，_)；return end，TOKEN＝'-1'；／*置标记，以下开始处理注解*／call GETCH(CH)；while 列计数≤行长-1 dobegin CH1:=CH；call GETCH(CH)；if CH1='*'and CH＝'/' ／*注解结束*／thenTOKEN:=''；end while；if TOKEN!=''then call PRINTERR('注解未完')；TOKEN:=''；returnend；3、模块7：识别界限符(RECOGDEL)输入：CH内含单界限符；输出：各种界符的TOKEN字；procedure RECOGDEL(CH，TOKEN)；begincase CH of'+':TOKEN:=('+'的种别码，_)；end；end...............end case；returnend；为了简明起见，模块7的说明中对各种同类情况的处理作了省略，读者可以完善。
如果嫌该模块大了一些，还可以对它再细分。
如果模块的长度在一页打印纸(≤60行)以内，则认为模块的大小是合适的。
由于把符号表和常数表合一，增加了查填符号表模块的复杂性。
需要填入符号表的单词有标识符，字符常数和数值常数。
它们填表的方法又各不相同。
标识符和字符常数都要求把字符串先填人字符串表，然后再把字符串在串表中的起点HEADP和长度LENGTH填入符号表的名字栏内。
对字符常数来说还要在TYPE栏内填入字符常数类型。
对数值常数而言，则把其值填入符号表的V AL栏内，同时在TYPE栏内填人该值的类型。
不管是标识符，字符常数，还是数值常数，在查填符号表时，首先检查是否有同名或同值入口项，如果有则直接返回该入口地址；否则将标识符或常数填入符号表中，并返回这个入口地址。
4、模块10：查填符号表(LOOKUP)输入：WORD,KIND；／*KIND区别WORD的类型*／输出：ENTRY；／*WORD在符号表中的入口*／procedure LOOKUP(WORD,KIND,ENTRY)；begincase KIND Of'标识符或字符串'：begin检查WORD是否与符号表某名字栏中的名字同名；／*包括类型检查*／if不同名thenbegin把WORD存入字符串表中，开始位置是HEADP；LENGTH：＝WORD中字符串的长度；ENTRY：＝P；／*P是符号表新入口*／NAME(P)：＝(HEADP，LENGTH)；if KIND=字符常数then TYPE：＝'字符常数'；endelse／*WORD和名字栏的入口Pi同名*／ENTRY:=Plend；'数字常数'：begin查检WORD是否和符号表VAL栏某入口同值；if不同值thenbegin V AL(P):=WORD；TYPE(P):=KIND；ENTRY:=P／*设P是符号表新入口*／endelse／*WORD和V AL栏的人口P1同值*／ENTRY:=P1end；end case；returnend；如果SIMPLE源程序中有以下说明语句：constant STRING1＝'CHAR_CONST'；PI＝3.1415；在执行SCANNER之后，STRING1，CHAR_CONST，PI和3．1415将要分别占用4个符号表入口项，这是不合理的。
由于词法分析程序不具备语法分析功能，也只能如此。
在语义分析阶段将可以解决这个问题，具体解决办法等到第六章再介绍。
最后再给出分类模块(SORT)的详细说明：模块3：单词分类模块(SORT)输入：CH内含单词首符；procedure SORT(CH)；begincase CH Of'字母'：call RECOGID(CH，TOKEN)；／*识别标识符*／'/'：call HANDLECOM(CH，TOKEN)；／*处理注解及界限符'/'*／'数字'：call RECOGDIG(CH，TOKEN)；／*识别数字常数*／：call RECOGSTR(CH，TOKEN)；／*识别字符常数*／otherwise call RECOGDEL(CH，TOKEN)；／*识别各种界符*／end case；write TOKEN into TOKEN文件；returnend；实验报告格式编译原理课程实验报告实验：词法分析实验例子：求最大值与最小值(存到一个.txt 文件)PROGRAM maxmin(input,output);V ARx,max,min,real;i:integer;BEGINread(x);write(x);max:=x;min:=x;FOR i:=2 TO 20 DOBEGINread(x);write(x);IF i MOD 5=0THEN writeln;IF x>maxTHEN max:=xELSE IF x<minTHEN min:=xEND;END.实验输出结果举例：1．“PROGRAM”：保留字；“maxmin”:标识符；“（”：界符；“input”: 标准文件；“，”：界符；“output”:标准文件；“）”：界符；“；”：界符实验二：LL（1）文法的判别实验目的：1．通过实验掌握确定的自顶向下语法分析方法的基本思想和技术；2．进一步巩固判别一个上下文无关文法是否是LL（1）文法的基本原理的掌握。
3．能够设计出计算一个文法的FIRST、FOLLOW、SELECT集合的算法。
实验原理：1．文法满足的条件：经过压缩，无左递归，无回溯。
2．基本思想：一个上下文无关文法是LL（1）文法的充分必要条件是，对每个非终结符A的两个不同产生式，A→α，A→β，满足：SELECT（A→α）∩SELECT（A→β）=φ，其中α，β不能同时推出空。
如果对于某个非终结符，它不含有空产生式，那么只要计算出它们右部的符号串可以推导出的首符号集合不相交，就可以根据当前的输入符号是属于哪个产生式右部的首符号集合而决定选择相应产生式进行推导。
FIRST（A→α）∩FIRST（A→β）=φ，其中α，β不能推出空。
如果当某一非终结符的产生式中含有空产生式时，它的非空产生式右部的首符号集合两两不相交，并与在推导过程中紧跟该非终结符右边可能出现的终结符集也不相交，则仍可构造确定的自顶向下分析。
FIRST（A→α）∩FOLLOW（A）=φ，其中α，β不能同时推出空。
这样只要计算出所有非终结符号的FIRST、FOLLOW集合，就可以计算出选择某个产生式的选择集合SELECT集合，这样就可以判断出给定的文法是否是LL（1）文法。
实验内容：1．设计求出能推出ε的非终结符的算法，并用程序实现FIRST、FOLLOW集合。
2．根据定义构造求FIRST、FOLLOW集合的算法，并用程序实现。