编译器笔记与实验记录

栏目: 服务器 · 编程工具 · 发布时间: 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算法

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

查看所有标签

猜你喜欢:

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

算法设计手册

算法设计手册

斯基恩纳 / 清华大学出版社 / 2009-9 / 69.00元

《算法设计手册(第2版)》是算法设计畅销书的最新版本,是设计实用且高效算法的最全面指导书。《算法设计手册(第2版)》揭密了算法的设计与分析,以简单易懂的写作风格,介绍了各种算法技术,着重强调了算法分析,全书包括两大部分,“技术”部分介绍了设计和分析计算机算法的各种方法,“资源”部分给出了大量的参考资源,以及算法实现的各种资源,此外,在作者的个人网址http://www.CS.sunysb.edu/......一起来看看 《算法设计手册》 这本书的介绍吧!

html转js在线工具
html转js在线工具

html转js在线工具

RGB CMYK 转换工具
RGB CMYK 转换工具

RGB CMYK 互转工具

HEX HSV 转换工具
HEX HSV 转换工具

HEX HSV 互换工具