傻瓜的解析器和编译器.从哪儿开始？

Question

这是一个很好的列表,但对于这个领域的完整newb来说,最好的是什么.一个来自更高级别背景的人(VB6,C#,Java,Python) - 不熟悉C或C++.在这个阶段,我对Lex/Yacc的手写解析更感兴趣.

如果我刚刚主修计算机科学而不是心理学,我可能会在大学里上课.那好吧.

Answer 1

请看一下:学习编写编译器

也很有趣:

• 如何编写编程语言
• 解析我在哪里可以了解它
• 解析器解释器和编译器的学习资源(好的,你已经提到了这个.

关于这个主题还有更多内容.但我可以简单介绍一下:

第一步是词法分析.字符流被转换为令牌流.令牌可以很简单,如== <= + - (等),它们可以像标识符和数字一样复杂.如果你愿意,我可以详细说明这一点.

下一步是将令牌流转换为syntaxtree或其他表示.这称为解析步骤.

在创建解析器之前,您需要编写语法.例如,我们创建一个表达式解析器:

令牌

addOp = '+' | '-';
mulOp = '*' | '/';
parLeft = '(';
parRight = ')';
number = digit, {digit};
digit = '0'..'9';

Each token can have different representations: + and = are both addOp and 
23 6643 and 223322 are all numbers.

语言

exp = term | exp, addOp, term;  
// an expression is a series of terms separated by addOps.
term = factor | term, mulOp, factor;
// a term is a series of factors separated by mulOps
factor = addOp, factor | parLeft, exp, parRight | number;
// a factor can be an addOp followed by another factor, 
// an expression enclosed in parentheses or a number.

词法分析员

我们创建一个状态引擎,遍历char流,创建一个令牌

s00 
  '+', '-' -> s01       // if a + or - is found, read it and go to state s01.
  '*', '/' -> s02
  '('      -> s03
  ')'      -> s04
  '0'..'9' -> s05
  whitespace -> ignore and retry  // if a whitespace is found ignore it
  else ERROR      // sorry but we don't recognize this character in this state.
s01
  found TOKEN addOp     // ok we have found an addOp, stop reading and return token
s02 
  found TOKEN mulOp
s03
  found TOKEN parLeft
s04
  found TOKEN parRight
s05
  '0'..'9'     -> s05    // as long as we find digits, keep collecting them
  else found number      // last digit read, we have a number

分析器

现在是时候创建一个简单的解析器/评估器了.这在代码中已完成.通常它们是使用表创建的.但我们保持简单.读取令牌并计算结果.

ParseExp
  temp = ParseTerm // start by reading a term
  while token = addOp do
    // as long as we read an addop keep reading terms
    if token('+') then temp = temp + ParseTerm  // + so we add the term
    if token('-') then temp = temp - ParseTerm  // - so we subtract the term
  od
  return temp // we are done with the expression

ParseTerm
  temp = ParseFactor
  while token = mulOp do
    if token('*') then temp = temp * ParseFactor
    if token('/') then temp = temp / ParseFactor
  od
  return temp

ParseFactor
  if token = addOp then
    if token('-') then return - ParseFactor  // yes we can have a lot of these
    if token('+') then return ParseFactor
  else if token = parLeft then
    return ParseExpression
    if not token = parRight then ERROR
  else if token = number then
    return EvaluateNumber   // use magic to translate a string into a number

这是一个简单的例子.在实际示例中,您将看到错误处理是解析器的重要组成部分.

我希望这有点澄清;-).