# Summer 2021: Parser Generator Targeting Julia (Answer)

## 提问1

描述下列文法能够解析的语言:

---

文法1:

a : a <A>
| <A>
;

> `<A>+`

文法2:

a : <A> a
  | <A>
  ;

> `<A>+`

文法3:

a : <A> | b
  ;
b : a <C> | <B>
  ;

> `(<A>|<B>)<C>*`

---

## 提问2

所有的terminal返回`token`类型的中间结果。 我们有以下的terminal:

1. `<name>`: 解析一个标识符
2. `"..."`: 解析双引号中的内容

假设我们有如下的外部变量，以OCaml语言的形式给出：

val get_str : token -> string
type expr = Fun  of string (* param *) * expr (* body *)
          | Call of expr * expr
          | Var  of string
          | Let  of string * expr * expr``

expr : "fun" <name> "->" expr { Fun(get_str($2), get_str($4)) }
     | "let" <name> "=" expr 
       "in" expr              { Let(get_str($2), $4, $6) }
     | call                   { $1 }
     ;
call : call atom  { Call($1, $2) }
     | atom       { $1 }
     ;
atom : <name>       { Var(get_str($1)) }
     | "(" expr ")" { $2 }
     ;

上述文法完整地描述了lambda calculus语言，并且是类型安全的。

那么，请问：

`expr`, `call`, `atom` 解析出的数据，分别是什么类型？

`expr` , `call` , `atom` 解析出的数据都是 `expr` 类型

---

## 提问3

给定文法：

a : a <A>  { $1 + 1 }
  | b      { $1 }
  ;

b : <B>  { 1 }
  | <C>  { 0 }
  ;

1. 对于一串token `| <C> | <A> | <A> |`, 上述文法的a规则是否能解析？ 如果可以，输出的结果是什么？
> 可以解析，结果为 ((0) + 1) + 1 = 2

2. 以a规则为起始规则，为该文法绘制一个流程图（在跳转分支的时候，可以不考虑跳转条件，直接连接当前节点与所有的后续节点）。

digraph hierarchy {
    nodesep=1.0

    a->{"a <A>" b}
    b->{"<B>" "<C>"}
}

3. 现在重新设计流程图，在所有表示non-terminal解析完成的节点上，附带解析结果。结果不一定要是具体的1, 0, 可以使用“一个整数”这样的描述。

digraph hierarchy {
    nodesep=1.0

    a->{"a <A>" b}
    b->{"<B>" "<C>"}
    "<B>" -> 1
    "<C>" -> 0
    "a <A>" -> 一个整数
}

4. 重新设计流程图，使得给定图中任意一个节点，都能得到完成解析需要的剩余完整路径（例如，有10条可能的路径，第一条是x1 -> x2 -> x3 -> ...)。

digraph hierarchy {
    nodesep=1.0

    a->{a1 b}
    b->{"<B>" "<C>"}
}