编译器笔记与实验记录

栏目: 服务器 · 编程工具 · 发布时间: 6年前

序言

  • 编译器,教程: http://mooc.study.163.com/learn/1000002001?tid=1000003000#/learn/content?type=detail&id=1000023001&cid=1000019000
  • 配套网站: http://staff.ustc.edu.cn/~bjhua/courses/compiler/2014/

正文

一. 编译器介绍

  • 概念: 编译器是一个程序,核心功能是把源程序代码翻译成为目标代码
  • 编译器核心功能如下图: 其中 静态计算 表示的是经过编译器后, 目标程序和源程序的功能需要相同

编译器笔记与实验记录

  • 解释器: 也是处理程序的一种程序;(解释器是在线的方式,也就是说解释器解释程序之后实际上还会执行该程序,而编译器只是生成可执行文件,称为离线形式, 编译器输出为可执行程序, 而解释器输出为程序执行结果)
  • 结构: 前端–>代码优化–>后端; 词法分析–>语法分析–>语义分析–>代码生成; (流水线模式)
  • 编译器结构: 如下图(一个没有优化的编译器结构)

编译器笔记与实验记录

  • 栈式计算机: 如:JVM

二. 词法分析

  • 编译器可以分为一个前端和后端, 前端又可细分为如下:

编译器笔记与实验记录

C

编译器笔记与实验记录

  • 词法分析的实现方法:
    1. 手工编码实现方法: 是目前非常流行的实现方法,如:GCC,LLVM
    2. 词法分析器的自动生成器: 可以快速成型,但是难以控制细节
  • 手工分析法: 转移图(实际上有点类似状态转移,需要注意的是有的地方需要回滚(回滚的实现: 一个可以通过文件指针的回退,另一个是可以将文件内容读取到一个字符数组中,然后需要回退时将索引减一即可))
  • 关键字表算法: 对给定语言的所有关键字构造一个Hash表,也就是对所有的标识符和关键字,先统一按标识符的转移图进行识别,识别完成后,再进一步查表看是否是关键字(关键字的完美Hash表: 完美哈希函数是没有冲突的的哈希函数,也就是,函数 H 将 N 个 KEY 值映射到 M 个整数上,这里 M>=N ,而且,对于任意的 KEY1 ,KEY2 ,H( KEY1 ) != H( KEY2 ) ,并且,如果 M = = N ,则 H 是最小完美哈希函数(Minimal Perfect Hash Function,简称MPHF) 参考博文 )
  • 自动生成法(生成器): 通过一些转换工具,如: lex,flex,jlex等将正则表达式转换为词法分析器; 需要用到:
    1. 正则
    2. 有限状态自动机: 输入的串是否能被状态机接受(DFA(确定的),NFA(不确定的))
    3. 正则表达式到 NFAThompson 算法,从 NFADFA 是子集构造算法,从DFA到词法分析器是Hopcraft最小化算法
  • DFA: 确定状态有限自动机(只有一个状态)(词法分析器是一个DFA); NFA: 非确定有限状态自动机(有多个状态)
  • 正则表达式转换为词法分析器:

编译器笔记与实验记录

  • DFA最小化算法: Hopcroft算法

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

Programming in Haskell

Programming in Haskell

Graham Hutton / Cambridge University Press / 2007-1-18 / GBP 34.99

Haskell is one of the leading languages for teaching functional programming, enabling students to write simpler and cleaner code, and to learn how to structure and reason about programs. This introduc......一起来看看 《Programming in Haskell》 这本书的介绍吧!

JSON 在线解析
JSON 在线解析

在线 JSON 格式化工具

UNIX 时间戳转换
UNIX 时间戳转换

UNIX 时间戳转换