Lab12 题解 (UCB CS61A@2021 Fall)

Regular Expressions

Q1: Calculator Ops

Write a regular expression that parses strings written in the 61A Calculator language and returns any expressions which have two numeric operands, leaving out the parentheses around them.

写一个符合 (operand operator1 operator2) 格式的正则表达式. 这个是比较简单的, 因为这里的运算符只有 +, -, *, /. 我们用 [] 括起来就可以, 但是要注意**- 需要用 \ 转义**

def calculator_ops(calc_str):
    """
    Finds expressions from the Calculator language that have two
    numeric operands and returns the expression without the parentheses.
    """
    return re.findall(r'[+\-*/] \d+ \d+', calc_str)

BNF

Q3: Linked List BNF

In this problem, we’re going to define a BNF that parses integer Linked Lists created in Python. We won’t be handling Link.empty.

For reference, here are some examples of Linked Lists:

Your implementation should be able to handle nested Linked Lists, such as the third example below.

• Link(2)
• Link(12, Link(2))
• Link(5, Link(7, Link(Link(8, Link(9)))))

要写一个能匹配链表(除了空结点的)的 Context-free grammar. 例子已经在问题的描述里面给出了

思路是这样的: 链表的开头肯定是 Link(, 然后我们可以把链表里面分为 link_first 和 link_rest 部分, 他们要么是数字, 要么就是另一个链表. 至于链表的语法是这样的: link_first 和 link_rest 有可能是链表也有可能是普通的数字; link_rest 可能是空的. 根据这些规则, 我们可以写出 BNF

link: "Link(" link_first ")" | "Link(" link_first "," link_rest ")"
?link_first: NUMBER | link
?link_rest: NUMBER | link

%ignore /\s+/
%import common.NUMBER

Q4: Tree BNF

Now, we will define a BNF to parse Trees with integer leaves created in Python.

Here are some examples of Trees:

Your implementation should be able to handle Trees with no branches and one or more branches.

• Tree(2)
• Tree(6, [Tree(1), Tree(3, [Tree(1), Tree(2)])])

给树定义一个 CFG:

1. tree_node: 可以是只有一个节点的树, 也可以是有结点还有分支的树, 注意分支可以有任意个(包括 0), 所以我们可以用正则表达式中的 +
2. ?label: 就是数字, 直接用 NUMBER 即可
3. branches: 可以是只有一个节点, 或者有多个节点(此时我们要把 , 号匹配进去)

tree_node: "Tree(" label ")" | "Tree(" label "," branches* ")"
?label: NUMBER
branches: "[" tree_node "]" | "[" tree_node "," tree_node+ "]"

%ignore /\s+/
%import common.NUMBER