尝试解析虚构的编程语言时出错

Question

我正在为我编写的编程语言开发语言解释器。这是一些示例代码，它应该可以工作，但目前在阅读此测试用例时死于 Syntax error at offset 45.。

{
  foo = { "min" : 1 ,"max" : 5};
  foo["min"]
}

正确的解释是第一行用foo创建一个map并存储在一个名为foo的变量中，第二行在记录foo中查找字段min的值，starting/ending 与分号一起将两个表达式包装成一个 expr_seq （即一个块），其计算结果与其中的最后一个 expr 相同。

我的parser.mly简化版如下：

%token <int> INT
%token <string> VAR
%token SEMI COMMA COLON ASSIGN QUOTE
%token LBRACK RBRACK LCURL RCURL
%token EOF

%start <int> main

%%

main:
| EOF
    { failwith "empty input" }
| e = exp EOF
    { e }

exp:
| INT
    { 0 }
| e = exp LBRACK v = q_var RBRACK
    { (* map lookup *) 0 }
| v = VAR ASSIGN e = exp
    { (* assign to var *) 0 }
| v = VAR LBRACK f = q_var RBRACK ASSIGN e = exp
    { (* assign to map field *) 0 }
| v = VAR
    { Printf.printf "lookup %s\n" v; 0 }
| LCURL e = expr_seq RCURL
    { (* Block expression *) 0 }
| LCURL f = fields RCURL
    { (* map literal *)0 }

fields:
| v = q_var COLON e = exp
    { [(v, e)] }
| v = q_var COLON e = exp COMMA vt = fields
    { (v, e) :: vt }

q_var:
| QUOTE v = VAR QUOTE
    { Printf.printf "qvar %s\n" v; v }

expr_seq:
| e = exp
    {[e]}
|e1 = exp SEMI e2 = expr_seq
    {e1 :: e2}

尝试自己调试它，我发现如果你删除以下 | v = VAR LBRACK f = q_var RBRACK ASSIGN e = exp 它会解析它并运行正确，但我真的很想能够设置一些东西在地图中。

我有 98% 的把握认为问题出在我的 mly 文件上，但是我的 lexer.mll 的简化版本如下：

{
  open Parser
  open Printf
}

rule token = parse
| [' ' '\t' '\n']
    { token lexbuf }
| "="
    {ASSIGN}
| ['1'-'9']['0'-'9']* as i
    { INT (int_of_string i) }
| ['a'-'z']+ as v
    { printf "var %s\n" v;VAR v }
| '{'
    { LCURL }
| '}'
    { RCURL }
| '['
    { printf "["; LBRACK }
| ']'
    { printf "]"; RBRACK }
| ';'
    { SEMI }
| ':'
    { COLON }
| ','
    { COMMA }
| '"'
    { QUOTE }
| eof
    { EOF }
| _
    { raise (Failure (sprintf "At offset %d: unexpected character.\n" 
                       (Lexing.lexeme_start lexbuf))) }

一个简单的 ml 文件是：

open Core.Std
open Printf

let rec read_all ic =
  try
    let ln = input_line ic in
      ln ^ read_all ic
  with End_of_file -> "";;

let () =
  let linebuf = Lexing.from_string (read_all stdin) in
  try
    Parser.main Lexer.token linebuf;
    printf "Done"
  with
  | Failure msg ->
      fprintf stderr "%s%!" msg
  | Parser.Error ->
      fprintf stderr "Syntax error at offset %d.\n%!"   
        (Lexing.lexeme_start linebuf)

编辑：这是一个 Makefile。 parser.mly、lexer.mll、interpreter.ml分别是上面的第二个、第三个、第四个文件。

all: HB lexer.cmx parser.cmx interpreter.cmx
    @true

HB: interpreter.cmx
    ocamlfind ocamlopt -o HB -linkpkg -package core -package core_kernel \
    -thread -w -10 parser.cmx lexer.cmx interpreter.cmx

interpreter.cmx: lexer.cmx
    ocamlfind ocamlopt -package core -package core_kernel -thread -w   -10 \
    -c interpreter.ml

lexer.cmx: lexer.ml parser.cmx
    ocamlfind ocamlopt    -c lexer.ml

parser.cmx: parser.mly
    menhir --ocamlc "ocamlfind ocamlc" --infer --base parser  parser.mly
    ocamlfind ocamlc -c parser.mli
    ocamlfind ocamlopt -c parser.ml

lexer.ml: lexer.mll
    ocamllex lexer.mll

clean:
    @rm HB *.o *.cmi *.cmx lexer.ml parser.ml parser.mli 2>/dev/null || true

这里是制作/运行宁它，其中 test.in 是上面的第一个。

$ mk;HB < test.in
ocamllex lexer.mll
menhir --ocamlc "ocamlfind ocamlc" --infer --base parser  parser.mly
15 states, 286 transitions, table size 1234 bytes
Warning: 3 states have shift/reduce conflicts.
Warning: 3 shift/reduce conflicts were arbitrarily resolved.
ocamlfind ocamlc -c parser.mli
ocamlfind ocamlopt -c parser.ml
ocamlfind ocamlopt    -c lexer.ml
ocamlfind ocamlopt -package core -package core_kernel -thread -w -10 \
    -c interpreter.ml
ocamlfind ocamlopt -o HB -linkpkg -package core -package core_kernel \
    -thread -w -10 parser.cmx lexer.cmx interpreter.cmx
Syntax error at offset 45.
var foo
var min
qvar min
var max
qvar max
var foo
[var min
]qvar min

编辑 2：我最后只是将 | e = VAR LBRACK v = q_var RBRACK { GetMap(v,LookupVar(e)) } 作为特例添加到我的解析器中。那么，问题解决了吗？

Answer 1

我试过你的语言，现在我同意解析器，你的输入不好，看看你的"assign to map field"规则：

v = VAR LBRACK f = q_var RBRACK ASSIGN e = exp

如果我们删除这个嘈杂的变量（你不需要使用，顺便说一句）：

VAR LBRACK q_var RBRACK ASSIGN exp

这意味着该规则期望：

VAR, '[' '"' VAR '"' ']' '=' exp

例如

foo["min"] = 42

以下完全接受

{
  foo = { "min" : 1 ,"max" : 5};
  foo["min"] = 42
}

Answer 2

回想起来，我认为它不起作用的原因是语法不是 LR(1)，因此 Menhir 无法准确解析。确定 foo["min"] 是 v = VAR LBRACK f = q_var RBRACK ASSIGN e = exp 的开始还是 e = exp LBRACK v = q_var RBRACK，需要我们向前看四个左右的符号，而 Menhir 作为 LR(1) 解析器只向前看一个。

尝试解析虚构的编程语言时出错

Error trying to parse imaginary programming language

ocaml

ocamllex

menhir