perl - 类 Lisp 语法用 perl 编译成 javascript

Question

作为学习 perl 的个人练习，我想在 perl 中为 javascript 编写一个“类似 lisp 的语法” 编译器。

“类 Lisp”，所以不是完整的 Lisp 实现，我希望最终的语法是“上下文无关”语法 (LALR)，并且相对容易编译成原生 Javascript。

制作词法分析器应该没有问题(可能用 Parse::Flex)，但需要帮助选择语法分析器生成器。

在 CPAN 中找到 3 个并且需要帮助选择/阅读:我应该学习什么 :)/以完成上述任务。

• yacc/bison 家族 - Parse::Yapp或 Parse::Eyapp
• Parse::RecDescent
• Marpa R2 (或 R3)或 Marpa_XS
• 或者其他我错过的东西...

问题是:

• 什么是最适合 lisp-like 语言的？
• 哪个学习曲线不那么陡峭(因此，存在很多学习示例)(例如，我只发现了很少的 Marpa 示例)

Answer 1

如果你只想解析 Lisp 的一个子集(尤其是 Scheme 的一个简单子(monad)集)，你可以自己编写那个解析器，m//gc 风格和一个堆栈:

sub parse {
  my $_ = shift;
  pos($_) = 0;
  my @stack = ([]);
  while (pos($_) < length($_)) {
    m/\G\s+/gc and next; # skip whitespace
    if (m/\G\(/gc) { # opening parens
      push @stack, [];
    } elsif (m/\G\)/gc) { # closing parens
      my $list = pop @stack;
      push @{ $stack[-1] }, $list;
    } elsif (m/([\w-.]+)/gc) { # identifiers, numbers
      push @{ $stack[-1] }, $1;
    } else {
      die "I'm at @{[pos($_)]} and I have no idea how to parse this";
    }
  }
  @stack == 1 or die "Closing parens expected at the end";
  return $stack[0];
}

这是相当小的，但可以解析基本的 Lisp。当您想要允许阅读器宏或准引号或字符串时，它会变得更加困难。还应该提供更好的错误消息。

有了Marpa，上面的循环不会有太大变化；代替pushing，我们会将 token 提供给识别器。

my $grammar = Marpa::R2::Grammar->new({
  ..., # some other options here
  soure => \(<<'END_OF_GRAMMAR),
  :start ::= Atom

  List ::= (ParenL) AtomList (ParenR) action => ::first
  Atom ::= List          action => ::first
       |   Number        action => ::first
       |   Identifier    action => ::first
  AtomList ::= Atom+
END_OF_GRAMMAR
});
$grammar->precompute; # compile the grammar

这需要终端符号 ParenL、ParenR、Number、Identifier。

在我们的parse 子程序中，我们首先必须创建一个新的识别器

my $rec = Marpa::R2::Recognizer({ grammar => $grammar });

并修改分词器循环中的操作:

my ($type, $value);
if (m/\G\(/gc) {
  ($type, $value) = (ParenL => undef);
} elsif (m/\G\)/gc) {
  ($type, $value) = (ParenR => undef);
} elsif (m/\G([0-9]+(?:\.[0-9]+))/gc) {
  ($type, $value) = (Number => $1);
} elsif (m/\G([\w-]+)/gc) {
  ($type, $value) = (Identifier => $1);
} else {
  die ...;
}
unless (defined $rec->read($type, $value) {
  die "Error at position @{[pos($_)]}. Expecting any of\n",
       map " * $_\n", @{ $rec->terminals_expected };
}

我们可以通过以下方式提取解析树

my $ref = $rec->value;
unless (defined $ref) {
  die "The input couldn't be parsed";
}
return $$ref;

在我们的例子中，解析树将是一堆嵌套的数组引用。但是您可以提供自定义操作，以便生成更复杂的 AST。例如。将树的每个节点祝福为一个对象，然后在根节点上调用 compile 可能是一种策略。