编译原理课程专题大纲

为了在将来更好地完成领域特定语言(DSL)的设计,2018年春学期,继2017年春学期对编译原理持续仅1个月的旁听经历后,我选择在今年继续完整旁听编译原理(CS131)课程。

在上海科技大学信息学院,CS131是一门被归入计算机科学与技术专业方向的面向本科生的4学分的专业选修课。每周共设2次时长各90分钟的讲座课,以及1次讨论课。设两类作业,编程作业(PA)与书面作业(WA)。

  • 概论
    • 上下文无关语法(Context-Free Grammar)
    • 需要研究的基本问题
  • 词法分析(Lexical Analysis)
    • 词法分析的总体流程
    • 基于双 buffer 的 token 扫读(Scanning)
    • 语言(Language)的严格定义及基本运算
    • 正则表达式(Regular Expression)的定义与基本定律
    • Token 的定义、识别,与基于状态转移图(Transition Diagram)的表示
    • 确定性(Deterministic)与非确定性有限自动状态机(Finite Automaton)的定义,与基于状态转移图/表的表示
    • DFA 与 NFA 的代码实现
    • NFA 向 DFA 的转换,与两者的特点比较
    • 正则表达式向 NFA 的转换
    • NFA 间的连接组合
    • 正则表达式向 DFA 的直接转换
    • DFA 的最简化
    • 使用 Flex 与 Lex
    • (考察大纲外)所有语言运算的对应 DFA 运算