3

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

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

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

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

问题是：

  • 什么最适合类 lisp 语言？
  • 哪一个的学习曲线不那么陡峭（因此，存在许多学习示例）（例如，我只找到了几个 Marpa 示例）
4

3 回答 3

4

如果您只想解析 Lisp 的一个子集（尤其是 Scheme 的一个简单子集），您可以自己编写该解析器，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。当您想要允许阅读器宏或准引号或字符串时，它会变得更加困难。还应该提供更好的错误消息。

使用马尔巴，上述循环不会有太大变化；我们将令牌提供给识别器，而不是pushing。

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。

在我们的parsesub 中，我们首先要创建一个新的识别器

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根节点可能是一种策略。

于 2013-05-08T08:35:10.403 回答
3

Lisp 系统本身不是使用解析器生成器构建的。Common Lisp 完全使用读取表进行解析，读取表将输入字符分类为各种类别。某些字符属于基于一两个字符组合触发注册功能的类别。一些字符类型被收集到标记中。血淋淋的细节在规范中。这个可读的想法来自 MacLisp（参见Lisp 进化的第 11 页）。

解析器生成技术（LALR(1) 及其同类技术）是由计算机科学家发明的，就像早在 1960 年代一样，他们一定感到受到新兴编程语言复杂语法的挑战。Lisp 黑客进入了更绿色的语义领域后，基本上拒绝了这一点，而是采取不发明不必要的问题（具有歧义的复杂的上下文无关语法）的立场，然后寻找复杂的解决方案（时间和空间高效的解析器，机器生成）。

所以如果你用这样的东西来解析 Lisp，你本质上就是在犯异端邪说。:)

请注意，在 TeX 中出现了与 Lisp 的 readtables 非常相似的东西：具有讽刺意味的是，该软件是由发明 LR 解析器的同一个人发明的。

于 2013-05-19T06:26:35.727 回答
2

恕我直言，您可以使用 yapp - lisp 具有简单的语法。检查这个问题。你应该检查 CPAN 的“ lisp ”和“ javascript ”，你会发现：

  • 非常新鲜的 CPAN 模块CljPerl - perl/lisp 桥
  • 模板::Javascript
  • 也许您应该检查Meta-Html（用 C 编写）和Sibilant.js（用 Javascript 编写并编译成 javascript）以了解您未来的“类 Lisp”语言的想法：）
于 2013-05-08T08:04:11.020 回答