编译原理标准实验报告.doc

编译原理实验报告江苏科技大学电子信息学院2005年8月19日 目 录 实验一：词法分析设计2实验二：LL(1)预测分析10实验三：逆波兰表达式的产生及计算26实验四：SLR(1)语法分析设计48实验五：应用DAG进行局部优化52实验一 词法分析设计一实验目的通过本实验的编程实践，使学生了解词法分析的任务，掌握词法分析程序设计的原理和构造方法，使学生对编译的基本概念、原理和方法有完整的和清楚的理解，并能正确地、熟练地运用。二实验内容用VC+/VB/JAVA语言实现对C语言子集的源程序进行词法分析。通过输入源程序从左到右对字符串进行扫描和分解，依次输出各个单词的内部编码及单词符号自身值；若遇到错误则显示“Error”，然后跳过错误部分继续显示 ；同时进行标识符登记符号表的管理。三实验步骤1基于实验的内容，构造程序所需的模块2根据已建构的模块，写出各个模块的相应程序代码3在主函数中调用模块来完成所要得到的效果四参考答案1源程序# # 存在问题：如何能较好的判断符号的优先级？ # #* 定义变量*Dim str_stack(1 To 20) As String, str_input As String, str_output As String, current As StringDim stack_p As Double, str_feihouzhui As String* 函数定义*Private Sub chansheng()Dim i As Double, j As Double, int_length As Long, stack_top As String, temp_stack_p As DoubleDim str_temp As String, int_length2 As Long, success As Boolean, str_temp_stack(1 To 20) As StringDim msg As Doublesuccess = TrueFor i = 1 To 20 str_stack(i) = Nextstr_input = : str_output = : current = i = 1: j = 1: stack_p = 1temp_stack_p = 0 用于存放优先级较高的运算符的临时堆栈的指针str_input = InputBox(请输入待转换的非后缀式：, 输入非后缀式, (a+b*c)*d, 3000, 5000) & #str_feihouzhui = str_inputint_length = Len(str_input)int_length2 = int_lengthgrid.Rows = 100 初始化表格控件grid.Cols = 4grid.TextMatrix(0, 0) = 当前符号grid.TextMatrix(0, 1) = 输入区grid.TextMatrix(0, 2) = 符号栈grid.TextMatrix(0, 3) = 输出区grid.ColWidth(0) = 2100 设置列宽grid.ColWidth(1) = 2100grid.ColWidth(2) = 2075grid.ColWidth(3) = 3100Do While (success)current = Mid(str_input, 1, 1)l0: stack_top = str_stack(stack_p)str_temp = Select Case current Case 0 To 9, a To z str_output = str_output & current int_length2 = int_length2 - 1 Case *, / Select Case stack_top Case str_stack(stack_p) = current int_length2 = int_length2 - 1 Case *, /, +, -, ( stack_p = stack_p + 1 str_stack(stack_p) = current int_length2 = int_length2 - 1 End Select Case +, - Select Case stack_top Case str_stack(stack_p) = current For j = temp_stack_p To 1 Step -1 If str_temp_stack(temp_stack_p) Then stack_p = stack_p + 1 str_stack(stack_p) = str_temp_stack(j) temp_stack_p = temp_stack_p - 1 End If Next int_length2 = int_length2 - 1 Case *, / str_output = str_output & str_stack(stack_p) 若优先级低于栈顶运算符，则弹出栈顶运算符并输出 If stack_p 1 Then stack_p = stack_p - 1 Else str_stack(stack_p) = End If GoTo l0 Case +, -, ( stack_p = stack_p + 1 str_stack(stack_p) = current int_length2 = int_length2 - 1 For j = temp_stack_p To 1 Step -1 If str_temp_stack(temp_stack_p) Then stack_p = stack_p + 1 str_stack(stack_p) = str_temp_stack(j) temp_stack_p = temp_stack_p - 1 End If Next End Select Case ( Select Case stack_top Case str_stack(stack_p) = current int_length2 = int_length2 - 1 Case *, /, +, -, ( stack_p = stack_p + 1 str_stack(stack_p) = current int_length2 = int_length2 - 1 End Select Case ) Select Case stack_top Case msg = MsgBox(错误，没有匹配的“（”。, 出错, 1) Case *, /, +, - str_output = str_output & str_stack(stack_p) If stack_p 1 Then stack_p = stack_p - 1 End If Case ( If stack_p 1 Then stack_p = stack_p - 1 Else str_stack(stack_p) = End If int_length2 = int_length2 - 1 End SelectEnd Selectstr_input = Right(str_input, int_length2)For j = 1 To stack_p str_temp = str_temp & str_stack(j)NextIf current = # Then For j = stack_p To 1 Step -1 If Not str_stack(stack_p) = Then str_output = str_output & str_stack(j) If stack_p 1 Then stack_p = stack_p - 1 Else str_stack(stack_p) = End If End If Next success = FalseEnd Ifgrid.TextMatrix(i, 0) = currentgrid.TextMatrix(i, 1) = str_inputgrid.TextMatrix(i, 2) = str_tempgrid.TextMatrix(i, 3) = str_outputi = i + 1LoopEnd SubPrivate Sub calculate()Dim msg As Double, int_length As Double, i As Double, j As Double, int_length2 As DoubleDim fuzhi(1 To 20) As String, m As Double, n As Double, int_temp As DoubleIf cmd_chansheng.Enabled = False Then msg = MsgBox(是否对已有逆波兰式进行计算？, vbYesNo, 提示) Select Case msg Case 6 GoTo l1 Case 7 Call chansheng End SelectElse Call chanshengEnd Ifl1: str_input = str_outputstr_temp = InputBox(请以“=”的形式给待求算术表达式中的变量赋值，注意，各变量间以“，”隔开。, 赋值, a=1,b=2,c=3,d=4, 3000, 5000)int_length2 = Len(str_temp)m = 1: n = 2For i = 1 To int_length2current = Mid(str_temp, i, 1)Select Case current Case a To z fuzhi(m) = current m = m + 2 Case 0 To 9 fuzhi(n) = current n = n + 2End SelectNextPicture1.Print 转换前的非后缀式为: & str_feihouzhuiPicture1.Print 待求的算术表达式为: & str_outputPicture1.Print 各变量的值为: & str_tempstack_p = 1int_length = Len(str_input)For i = 1 To int_lengthcurrent = Mid(str_input, i, 1)Select Case current Case a To z For j = 1 To m Step 2 If current = fuzhi(j) Then str_stack(stack_p) = fuzhi(j + 1) End If Next stack_p = stack_p + 1 Case + stack_p = stack_p - 1 int_temp = CDbl(str_stack(stack_p - 1) + CDbl(str_stack(stack_p) str_stack(stack_p - 1) = CStr(int_temp) Case - stack_p = stack_p - 1 int_temp = CDbl(str_stack(stack_p - 1) - CDbl(str_stack(stack_p) str_stack(stack_p - 1) = CStr(int_temp) Case * stack_p = stack_p - 1 int_temp = CDbl(str_stack(stack_p - 1) * CDbl(str_stack(stack_p) str_stack(stack_p - 1) = CStr(int_temp) Case / stack_p = stack_p - 1 int_temp = CDbl(str_stack(stack_p - 1) / CDbl(str_stack(stack_p) str_stack(stack_p - 1) = CStr(int_temp) Case 0 To 9 str_stack(stack_p) = current stack_p = stack_p + 1 End SelectNextIf str_stack(stack_p) ThenPicture1.Print 计算结果为: & str_stack(stack_p - 1)End IfEnd Sub* 定义操作*Private Sub cmd_chansheng_Click()cmd_chansheng.Enabled = Falsecmd_calculate.Enabled = TrueCall chanshengEnd SubPrivate Sub cmd_calculate_Click()cmd_calculate.Enabled = FalseCall calculateEnd SubPrivate Sub cmd_exit_Click()EndEnd SubPrivate Sub cmd_main_Click()Form3.HideForm_main.ShowEnd SubPrivate Sub cmd_previous_Click()Form3.HideForm2.ShowEnd SubPrivate Sub cmd_reflesh_Click()cmd_chansheng.Enabled = Truecmd_calculate.Enabled = Truegrid.ClearPicture1.ClsEnd Sub2运行结果实验二 LL(1)预测分析一实验目的 通过完成预测分析法的语法分析程序，了解预测分析法和递归子程序法的区别和联系。使学生了解语法分析的功能，掌握语法分析程序设计的原理和构造方法，训练学生掌握开发应用程序的基本方法。有利于提高学生的专业素质，为培养适应社会多方面需要的能力。二实验内容1. 对下列文法，用LL（1）分析法对任意输入的符号串进行分析： （1）E-TG（2）G-+TG|TG（3）G-（4）T-FS（5）S-*FS|/FS（6）S-（7）F-(E)（8）F-i2. 构造预测分析表，并利用分析表和一个栈来实现对上述程序设计语言的分析程序。三实验步骤1基于实验的内容，构造程序所需的模块2根据已建构的模块，写出各个模块的相应程序代码3在主函数中调用模块来完成所要得到的效果四参考答案1源程序Option ExplicitDim zjf As StringDim stack(50) As StringDim qu(50) As StringDim m, n As IntegerPrivate Sub Form_Activate() RichTextBox1.Width = Me.Width RichTextBox1.Height = CFFX.HeightEnd SubPrivate Sub Toolbar1_ButtonClick(ByVal Button As ComctlLib.Button)Dim FileName As StringDim k, t As IntegerDim es As Integerk = 0Select Case Button.KeyCase Is = xj RichTextBox1.Text = RichTextBox1.Width = Me.Width RichTextBox1.Height = CFFX.Height MSFlexGrid1.Visible = False RichTextBox1.Visible = TrueCase Is = dk CommonDialog1.Filter = TXT文件|*.TXT 打开文件对话框 CommonDialog1.ShowOpen FileName = CommonDialog1.FileName RichTextBox1.FileName = FileName RichTextBox1.Width = Me.Width RichTextBox1.Height = CFFX.Height StatusBar1.Panels(1).Text = 徐天霞 & FileName MSFlexGrid1.Visible = False RichTextBox1.Visible = TrueCase Is = bc CommonDialog1.DialogTitle = 保存 CommonDialog1.Filter = 文本文件(*.txt)|*.txt CommonDialog1.ShowSave FileName = CommonDialog1.FileName RichTextBox1.SaveFile FileName StatusBar1.Panels(1).Text = 徐天霞 & FileName Case Is = fxWhile Mid(RichTextBox1.Text, k + 1, 1) qu(k) = Mid(RichTextBox1.Text, k + 1, 1) k = k + 1Wend MSFlexGrid1.Clear es = LL() RichTextBox1.Width = Me.Width RichTextBox1.Height = Me.Height / 2 MSFlexGrid1.Visible = True If es 0 Then MsgBox 分析成功！ Else MsgBox 分析失败！ End If For t = 0 To 49 qu(t) = Next tCase Is = tc Unload MeEnd SelectEnd SubPublic Function LL() As IntegerDim i, j As IntegerDim F As BooleanDim k As IntegerDim char2 As StringWith CFFX.MSFlexGrid1 .Cols = 5 .Rows = 100 For k = 1 To 4 .ColWidth(k) = 1600 Next k .Row = 0 .Col = 0 .Text = 步 骤 .Col = 1 .Text = 分析栈 .Col = 2 .Text = 剩余输入串 .Col = 3 .Text = 所用产生式 .Col = 4 .Text = 动 作 End Withn = 0m = 1zjf = i()+-*/stack(0) = #stack(1) = EF = Truej = 1i = 0With CFFX.MSFlexGrid1 .Row = m .Col = 0 .Text = Str(n) .Col = 1 k = 0 char2 = While stack(k) char2 = char2 & stack(k)k = k + 1Text = char2Wend.Col = 2k = 0char2 = While qu(k) char2 = char2 & qu(k) k = k + 1 .Text = char2 Wend.Col = 3.Text = .Col = 4.Text = 初始化 End With m = m + 1n = n + 1While F If InStr(zjf, stack(j) Then If stack(j) = qu(i) Then qu(i) = i = i + 1 stack(j) = j = j - 1 With CFFX.MSFlexGrid1 .Row = m .Col = 0 .Text = Str(n) .Col = 1 k = 0 char2 = While stack(k) char2 = char2 & stack(k) k = k + 1 .Text = char2 Wend .Col = 2 k = 0 char2 = While qu(k) char2 = char2 & qu(k) k = k + 1 .Text = char2 Wend .Col = 3 .Text = .Col = 4 .Text = GETNEXT(I) End With m = m + 1 n = n + 1 Else LL = 0 Exit Function End If Else If stack(j) = # Then If stack(j) = qu(i) Then F = False LL = 1 Exit Function Else LL = 0 Exit Function End If Else Select Case stack(j) Case E If qu(i) = i Or qu(i) = ( Then stack(j) = G j = j + 1 stack(j) = TWith CFFX.MSFlexGrid1 .Row = m .Col = 0 .Text = Str(n) .Col = 1 k = 0 char2 = While stack(k) char2 = char2 & stack(k) k = k + 1 .Text = char2 Wend .Col = 2 k = 0 char2 = While qu(k) char2 = char2 & qu(k) k = k + 1 .Text = char2 Wend .Col = 3 .Text = E-TG .Col = 4 .Text = POP,PUSH(GT) End Withm = m + 1 n = n + 1ElseLL = 0 Exit Function End If Case T If qu(i) = i Or qu(i) = ( Then stack(j) = S j = j + 1 stack(j) = F With CFFX.MSFlexGrid1 da ying .Row = m .Col = 0 .Text = Str(n) .Col = 1 k = 0 char2 = While stack(k) char2 = char2 & stack(k) k = k + 1 .Text = char2 Wend .Col = 2 k = 0 char2 = While qu(k) char2 = char2 & qu(k) k = k + 1 .Text = char2 Wend .Col = 3 .Text = T-FS .Col = 4 .Text = POP,PUSH(SF) End With m = m + 1 n = n + 1 Else LL = 0 Exit Function End If Case G If qu(i) = + Then stack(j) = G j = j + 1 stack(j) = T j = j + 1 stack(j) = +ith CFFX.MSFlexGrid1 da ying .Row = m .Col = 0 .Text = Str(n) .Col = 1 k = 0 char2 = While stack(k) char2 = char2 & stack(k) k = k + 1 .Text = char2 Wend .Col = 2 k = 0 char2 = While qu(k) char2 = char2 & qu(k) k = k + 1 .Text = char2 Wend .Col = 3 .Text = G-+TG .Col = 4 .Text = POP,PUSH(GT+) End With m = m + 1 n = n + 1 Else If qu(i) = - Then stack(j) = G j = j + 1 stack(j) = T j = j + 1 stack(j) = - With CFFX.MSFlexGrid1 da ying .Row = m .Col = 0 .Text = Str(n) .Col = 1 k = 0 char2 = While stack(k) char2 = char2 & stack(k) k = k + 1 .Text = char2 Wend .Col = 2 k = 0 char2 = While qu(k) char2 = char2 & qu(k) k = k + 1 .Text = char2 Wend .Col = 3 .Text = G-TG .Col = 4 .Text = POP,PUSH(GT-)End With m = m + 1 n = n + 1 ElseIf qu(i) = ) Or qu(i) = # Then stack(j) = j = j - 1With CFFX.MSFlexGrid1 da ying .Row = m .Col = 0 .Text = Str(n) .Col = 1 k = 0 char2 = While stack(k) char2 = char2 & stack(k) k = k + 1 .Text = char2 Wend .Col = 2 k = 0 char2 = While qu(k) char2 = char2 & qu(k) k = k + 1 .Text = char2 Wend .Col = 3 .Text = G- .Col = 4 .Text = POP End With m = m + 1 n = n + 1 Else LL = 0 Exit Function End If End If End If Case S If qu(i) = * Then stack(j) = S j = j + 1 stack(j) = F j = j + 1 stack(j) = * With CFFX