ZUCC_编译语言原理与编译_实验05 正则表达式、有限自动机、词法分析

编译语言原理与编译实验报告

课程名称	编程语言原理与编译
实验项目	正则表达式、有限自动机、词法分析

实验内容

一、阅读课件，阅读教材第2章

1. 理解词元token的概念，理解词元类型，词元语义值

   • 词元是具有独立含义的最小语法单位
   • 标识符 (变量名，函数名，类名……)；关键字 (if while for function static)；常数 ( Int ,Float, Complex,Boolean,Symbol…)；运算符 (+ - * / ^ *= :=)；分界符 ([ ] {} () ; ,)；字符串 (“asf”)
   • 对于标识符一般为符号表内序号，对于关键字和运算符和分界符可以为空，对于常数和字符串为自己本身或符号表内序号

2. 理解正则表达式的基本情况，与组合方法（选择、连接、重复）

   • 正则表达式是表示符合特定格式的字符串模式，用来描述词元的结构
   • 如果r和s都是正则表达式，分别表示语言L和L(s)，那么:
     • r|s是一个正则表达式，表示的语言是L(r)∪L(s)
     • rs是一个正则表达式，表示语言L(r)•L(s)
     • r*是一个正则表达式，表示语言(L(r))*

3. 理解 最长匹配，优先次序

   • 当输入串的前缀与多个终态匹配成功时,总是选择最长的前缀进行匹配
   • ‘*’ > ‘.’ > ‘|’，后两个均为左结合

4. 理解 p13 2-1 2-2

5. 理解 NFA 、DFA，DFA最小化方法

   1. 确定性有限自动机(DFA): 对于给定的输入符号，只做唯一的动作（没有ε边转移）
   2. 非确定性有限自动机(NFA): 对于同一个输入符号，存在多种动作可选
   3. 将状态集合作为一个状态。考察在子集上的每个状态的迁移是否等价，如果等价，则这些状态是可以合并的。

6. Automata.js 输入正则表达式，查看结果

二、写出下面的正则表达式

1、制表符\t和空格的任意序列 \t \t

^(\t|\s)*$

2、C/C++ 语言的注释 // /* a/**/sfasfd */ 注意查找网络资源

/\*[^*]*\*+([^/*][^*]*\*+)*/

https://blog.csdn.net/zhangpeterx/article/details/88115338

3、字符串常量 “this is a string”

^"[a-zA-Z\s]+"$

4、浮点数 3.14159

^(-?\d+)(\.\d+)?$

https://blog.csdn.net/weixin_39867296/article/details/111611301

学习 URL 匹配的正则表达式的例子

(https?|ftp|file)://[-A-Za-z0-9+&@#/%?=~_|!:,.;]+[-A-Za-z0-9+&@#/%=~_|]

https://www.cnblogs.com/speeding/p/5097790.html

三、请结合实际例子说明什么是（ p13）最长匹配规则、规则次序优先

最长匹配规则: 对于输入的子串‘if8’, 它可以和保留字‘if’匹配两个字符,也可以与标识符匹配三个字符, 这里优先选择较长的匹配. 因此‘if8’是标识符. 再例如使用正则匹配中的贪婪匹配, 比如表达式: a.*b来匹配ababab, 它就会匹配到尽可能长的字符串, 这里是ababab.g

规则次序优先: 对于输入的子串‘if 89’, 第一个与之匹配的是保留字‘if’, 因此改子串以保留字开头.

四、考虑下面的正则表达式, 画出相应的NFA/DFA

$$\begin{gathered} (ab|ac{)}^{\ast } \\ (0|1{)}^{\ast }11001^{\ast } \\ (01|10|00{)}^{\ast }11 \end{gathered}$$

1、构造 NFA

2、构造 DFA

3、最小化 DFA

五、学习 code/lex.zip 了解 lex 词法生成工具的运行原理

在实际编译器中 词法分析器Lexer ，是被语法分析器Parser 调用，具体见后面题目 calcvar 代码

Lex 是一个词法分析器的生成工具，它支持使用正则表达式来描述各个词法单元的模式，由此给出一个词法分析器的规约，并生成相应的实现代码。 Lex 程序的输入方法称为 Lex 语言，而 Lex 程序本身被称为 Lex 编译器，Flex 是 Lex 编译器的一种替代实现( lex，flex 的关系和 cc，gcc 的关系很相似)。

Lex 程序的使用方法如下图所示:

一个 Lex 程序通常具有如下几个部分组成:

• 声明部分: 声明部分通常包括变量，明示常量和正则表达式的定义，明示常量是一个值为数字的标识符，用来表示词法单元的类型。
• 转换规则: 转换规则具有如下的形式: 模式 { 动作 }。每个模式是一个正则表达式，可以使用声明部分给出的正则定义。动作部分是代码片段，通常用 C 语言编写。
• 辅助函数: 这个部分中定义了各个动作所需要的函数，也可以包含 main 函数，这部分的代码将会放到输出的 C 代码中。

Lex 程序的工作方式:

Lex 程序提供了一个函数int yylex()和两个变量yyleng，yytext供外部(通常是语法分析器)读取，调用。

当调用yylex的时候，程序会从yyin指针所指向的输入流中逐个读入字符，程序发现了最长的与某个模式 Pi 匹配的字符串后，会将该字符串存入到yytext变量中，并设置yyleng变量为该字符串的长度，该字符串也就是词法分析程序分析出来的一个词法单元。

然后，词法分析程序会执行模式 Pi 对应的动作 Ai，并使用yylex函数返回 Ai 的返回值(通常是词法单元的类型)。

https://www.bwangel.me/2019/12/15/flex/

六、查看仓库 https://gitee.com/sigcc/plzoofs 目录 calcvar 语言程序

1、将程序编译，运行，https://gitee.com/sigcc/plzoofs/blob/master/calcvar/README.markdown 参考说明以调试模式运行

查看词元token，语法树

2、理解环境中变量值的绑定与存储

编译原理（十九）——运行时存储空间管理（变量访问环境）_很注重数学和821的博客-CSDN博客

3、理解 其中词法描述文件 lexer.fsl 的代码

Random coding knowledge | Using FSLexYacc, the F# lexer and parser (thanos.codes)

4、初步理解语法描述文件 parser.fsy 的代码

dotnet run -vn 查看 dotnet 调用词法分析器生成工具的命令，内容如下，具体路径有差异

dotnet "C:\Users\gm\.nuget\packages\fslexyacc\10.2.0\build\/fslex/netcoreapp3.1\fslex.dll"  -o "Scanner.fs" --module Scanner --unicode Scanner.fsl
...  
dotnet "C:\Users\gm\.nuget\packages\fslexyacc\10.2.0\build\/fsyacc/netcoreapp3.1\fsyacc.dll"  -o "Parser.fs" --module Parser Parser.fsy

dotnet "C:\Users\shuhe\.nuget\packages\fslexyacc\10.2.0\build\fslex\netcoreapp3.1\fslex.dll"  -o "Scanner.fs" --module Scanner --unicode Scanner.fsl

dotnet "C:\Users\shuhe\.nuget\packages\fslexyacc\10.2.0\build\/fsyacc\netcoreapp3.1\fsyacc.dll"  -o "Parser.fs" --module Parser Parser.fsy

理解fsproj 项目文件的参数，这些参数会传递给上面的命令

<FsLex Include="lexer.fsl">
<OtherFlags>--module Lexer --unicode</OtherFlags>
</FsLex>
<FsYacc Include="parser.fsy">
<OtherFlags>--module Parser</OtherFlags>
</FsYacc>

【译】Python Lex Yacc手册 - P_Chou - 博客园 (cnblogs.com)

七、学习 CLex.fsl 结构，理解 MicroC 的词法分析器

用调试模式运行microC 解释器，编译器 -g 具体见 ReadME.md

  dotnet build -v n interpc.fsproj 

dotnet "C:\Users\shuhe\.nuget\packages\fslexyacc\10.2.0\build\fslex\netcoreapp3.1\fslex.dll"   -o "CLex.fs" --module CLex --unicode CLex.fsl

  dotnet "C:\Users\shuhe\.nuget\packages\fslexyacc\10.2.0\build\/fsyacc\netcoreapp3.1\fsyacc.dll"  -o "CPar.fs" --module CPar CPar.fsy

理解 词元的含义，注意词元的类型，和对应的语义值<Type,Value>

• “token”一词有不少书将它翻译成“记号”，我们认为比较贴切的翻译应当是“单词符号”。它是程序设计语言中“具有独立含义的最小词法单位”，在这个意义上与我们自然语言中的“单词”的词义相同。但是，它又不完全相同，因为这里的“token”不仅仅包括“词”，而且还包括标点符号、操作符、分隔符等。将它翻译成“单词符号”正是为了体现这–点。但为了简洁起见，我们使用“单词”一词。-—译者注

• VOID 语义值与类型同

• NAME “n” 类型是NAME 语义值是 “n”

• CSTINT 1 类型是 CSTINT 语义值是“1”

~ microc>dotnet run -p .\interpc.fsproj -g ex1.c 8
Micro-C interpreter v 1.1.0 of 2021-3-22
interpreting ex1.c ...inputargs:[8]
Token:
VOID, NAME "main", LPAR, INT, NAME "n", RPAR, LBRACE, WHILE, LPAR, NAME "n", GT, CSTINT 0, RPAR, LBRACE, PRINT, NAME "n", SEMI, NAME "n", ASSIGN, NAME "n", MINUS, CSTINT 1, SEMI, RBRACE, PRINTLN, SEMI, RBRACE, EOF

理解关键字的处理

• 标识符 Name 放到关键字函数keyword的最后处理

理解注释 的处理

• // 单行

  • 单行注释处理规则，调用响应处理函数,

  • //参数是 lexbuf

    // 处理完后 lexbuf 内容已经更新，注释部分过滤

    //调用 Token 规则函数继续注释部分后面的处理

    | “/*” { Comment lexbuf; Token lexbuf } // 多行注释，调用 Comment规则

• /* */ 多行

  • 多行注释，调用 Comment规则,

  • and Comment = parse

    | “/*” { Comment lexbuf; Comment lexbuf } // 注释的嵌套处理

    | “*/” { () } // 注释处理结束

    | ‘\n’ { lexbuf.EndPos <- lexbuf.EndPos.NextLine; Comment lexbuf } //注释跨行处理

    | (eof | ‘\026’) { failwith “Lexer error: unterminated comment” } // 多行注释未封闭

    | _ { Comment lexbuf } // 其他任意情况都继续处理后续字符

    and EndLineComment = parse

    | ‘\n’ { lexbuf.EndPos <- lexbuf.EndPos.NextLine } //更新行尾位置，返回

    | (eof | ‘\026’) { () } // 文件结束，26 是 CTRL+Z的ASCII码，也是结束符 , () 退出返回

    | _ { EndLineComment lexbuf } // 继续读lexbuf 中下个字符

理解空白 换行 的处理

• | '\n'            { lexbuf.EndPos <- lexbuf.EndPos.NextLine; Token lexbuf } // 换行处理
                                                                             // EndPos 是内置类型 Position的实例，表示当前行的结束位置
  

理解字符串的处理 （MicroC 只做了词法分析，没有完整实现）

• | ‘"’ { CSTSTRING (String [] lexbuf) } // 调用字符串处理规则

•   and String chars = parse 
      | '"'
          { Microsoft.FSharp.Core.String.concat "" (List.map string (List.rev chars)) } 
                                                            // 字符串结束，通过字符数组chars构造字符串
                                                            // 由于构造的时候是列表 cons ::操作
                                                            // 这里需要用List.rev 翻转字符数组
                                                            // :: 是说 加在前面吗
      | '\\' ['\\' '"' 'a' 'b' 't' 'n' 'v' 'f' 'r']   //字符串 "\a" 读入后词法分析器 看到的是 "\\a"
          { String (cEscape (lexemeAsString lexbuf) :: chars) lexbuf }
      | "''" 
          { String ('\'' :: chars) lexbuf }
      | '\\'
          { failwith "Lexer error: illegal escape sequence" }
      | (eof | '\026')       { failwith "Lexer error: unterminated string" } 
                                                       // 字符串中出现文件结束
    
      | ['\n' '\r']  { failwith "Lexer error: newline in string" }  //字符串中出现回车
    
      | ['\000'-'\031' '\127' '\255']    
          { failwith "Lexer error: invalid character in string" }  // 字符串中出现 ASCII 控制字符
      | _
          { String (char (lexbuf.LexemeChar 0) :: chars) lexbuf } // 将读到的第1个字符加到临时的chars数组
    
  

理解转义字符的处理 （MicroC 只做了词法分析，没有完整实现）

•   // 字符串转义符处理函数
    let cEscape s = 
        match s with 
        | "\\\\" -> '\\'
        | "\\\"" -> '\"'
        | "\\a"  -> '\007'
        | "\\b"  -> '\008'
        | "\\t"  -> '\t'
        | "\\n"  -> '\n'
        | "\\v"  -> '\011'
        | "\\f"  -> '\012'
        | "\\r"  -> '\r'
        | _      -> failwith "Lexer error: impossible C escape"
  

八、大作业分组，并确定语言 Decaf/MicroC/ Tiger 。。。开始实现词法分析器(自选语言)

• 大作业词法部分

• 阅读语言规范 用 fslex 实现其词法分析器

  • 教材附录p360页 Tiger 语言规范

• 注意嵌套注释实现 /* /* */ */

• 注意字符串实现 "" '' " ' ' "

九、阅读书籍

• 计算的本质 第3章 自动机部分 ，理解采用表驱动方法手工实现NFA，DFA的技术
  https://bb.zucc.edu.cn/bbcswebdav/users/j04014/books/Understanding.Computation

  • Ruby 语言使用见 第1章

  • 第2章 的内容后面学习会用到，提前预习下

十、（自选）阅读JFLAP-simple tutorial.pdf 用JFLAP中构造上题目4 的NFA/DFA,并截图,保留文件. JFLAP在bb 上 soft 目录中,运行方式为

java -jar JFLAP.jar