Hw10 - CS61A of UCB(2021-Fall)
BNF
Q1: Grouping and Pipes
In this question, you will add support for grouping and piping.
Recall that grouping allows for an entire regular expression to be treated as a single unit, and piping allows for a pattern to match an expression on either side. Combined, these will let us create patterns which match multiple strings!
Define the
group
andpipe
expressions in your grammar.
- A
group
consists of anyregex
expression surrounded by parentheses (()
).- A
pipe
operator consists of aregex
expression, followed by a pipe (|
) character, and lastly followed by anotherregex
expression.For example,
r"apples"
would match exactly the phrase “apples” in an input. If we wanted our pattern from before to match “oranges” as well, we could expand ourrstring
to do so using groupings and pipes:r"(apples)|(oranges)"
.Hint: note that
group
s andpipe
s are validregex
expressions on their own! You may need to update a previously defined expression.
给本来用来匹配正则表达式的 BNF 添加功能: group
和 pipe
. 其实怎么实现这一写已经在描述里面给出了, 我这里就提一点: group
和 pipe
本身也是 ?regex
的一部分, 所以要把他们加到 ?regex
里面
?start: rstring
rstring: "r\"" regex* "\""
?regex: character | word | group | pipe
group: "(" regex* ")"
pipe: regex "|" regex
character: LETTER | NUMBER
word: WORD
%ignore /\s+/
%import common.LETTER
%import common.NUMBER
%import common.WORD
Q2: Classes
Now, we will add support for character classes.
Recall that character classes allow for the pattern to match any singular
character
defined within the class. The class itself consists either of individualcharacter
s, orrange
s ofcharacters
.Specifically, we define the following:
- A
range
consists of eitherNUMBER
s orLETTER
s separated by a hyphen (-
).- A
class
expression consists of any number ofcharacter
s or characterrange
s surrounded by square brackets ([]
).Note that for this question, a range may only consist of either
NUMBER
s orLETTER
s; this means that while[0-9]
and[A-Z]
are valid ranges,[0-Z]
would not be a valid range. In addition, thecharacter
s andrange
s in aclass
may appear in any order and any number of times. For example,[ad-fc0-9]
,[ad-f0-9c]
,[a0-9d-fc]
, and[0-9ad-fc]
are all valid classes.
这次要加上的功能是 ?-?
和 []
的功能, 具体怎么做同样在问题描述里面给出了. 这里讲一下注意的点:
range
的-
左右两边要是对应的, 所以character "-" character
这种写法是错的- 在
[]
里, 要么是range
, 要么是character
, 可以用(range|character)
表示,后面用*
表示 any number []
本身也是合法的正则表达式, 所以要放在?regex
里面
?start: rstring
rstring: "r\"" regex* "\""
?regex: character | word | group | pipe | class
group: "(" regex* ")"
pipe: regex "|" regex
range: NUMBER "-" NUMBER | LETTER "-" LETTER
class: "[" (range|character)* "]"
character: LETTER | NUMBER
word: WORD
%ignore /\s+/
%import common.LETTER
%import common.NUMBER
%import common.WORD
Q3: Quantifiers
Lastly, we will add support for quantifiers.
Recall that quantifiers allow for a pattern to match a specified number of a unit.
Specifically, we define the following:
- A
plus_quant
expression consists of agroup
, acharacter
, or aclass
, followed by a plus symbol (+
).- A
star_quant
expression consists of agroup
, acharacter
, or aclass
, followed by a star symbol (*
).- A
num_quant
expression consists of either agroup
, acharacter
, or aclass
, followed by one of the following:
- a
NUMBER
enclosed in curly braces ({}
);- a range of
NUMBER
s (separated by a comma (,
), which may potentially be open on only one side. For example,{2,7}
,{2,}
, and{,7}
are valid numeric quantifiers.{,}
is not valid.Hint: these three quantifiers share many similarities. Consider defining additional expressions in this question!
可以发现这三个 _quant
都是 group
或者 character
或者 class
开头, 所以这里可以定义一个 ?tmp: class | group | character
避免重复. 同时定义 ?quants: plus_quant | star_quant | num_quant
, 放在 ?regex
里
这里 num_quant
需要枚举下面这几种情况
{NUMBER, NUMBER}
or{NUMBER}
->(NUMBER (",", NUMBER)?)
{NUMBER,}
->(NUMBER ",")
{,NUMBER}
->("," NUMBER)
rstring: "r\"" regex* "\""
?regex: character | word | group | pipe | class | quants
group: "(" regex* ")"
pipe: regex "|" regex
range: NUMBER "-" NUMBER | LETTER "-" LETTER
class: "[" range* character* range* character* "]"
?tmp: class | group | character
plus_quant: tmp "+"
star_quant: tmp "*"
num_quant: tmp "{" ((NUMBER ("," NUMBER)?) | (NUMBER ",") | ("," NUMBER)) "}"
?quants: plus_quant | star_quant | num_quant
character: LETTER | NUMBER
word: WORD
%ignore /\s+/
%import common.LETTER
%import common.NUMBER
%import common.WORD
SQL
Q4: Size of Dogs
The Fédération Cynologique Internationale classifies a standard poodle as over 45 cm and up to 60 cm. The
sizes
table describes this and other such classifications, where a dog must be over themin
and less than or equal to themax
inheight
to qualify as asize
.Create a
size_of_dogs
table with two columns, one for each dog’sname
and another for itssize
.
要根据狗的体型大小来决定它的 size
. 这个就是一个基本的 select ... from ... where
的写法. 我们这里可以把两个表连接起来得到所有可能的结果, 然后用 where
来选出符合条件的.
注意这里用 alias 会比较简洁
CREATE TABLE size_of_dogs AS
SELECT d.name, s.size
FROM dogs as d, sizes as s
where d.height <= s.max and d.height > s.min;
Q5: By Parent Height
Create a table
by_parent_height
that has a column of the names of all dogs that have aparent
, ordered by the height of the parent from tallest parent to shortest parent.
用 ORDER BY
来进行排序, 注意是降序所以用 DESC
CREATE TABLE siblings AS
SELECT p1.child AS dogone, p2.child AS dogtwo, s1.size AS dogonesize, s2.size AS dogtwosize
FROM parents AS p1, parents AS p2, size_of_dogs AS s1, size_of_dogs AS s2
WHERE p1.parent = p2.parent AND p1.child < p2.child AND p1.child = s1.name AND p2.child = s2.name;
-- Use `<` to filter the result
-- `!=` is not enough, you will get `barack clinton` and `clinton barack` in the same time
Q6: Sentences
There are two pairs of siblings that have the same size. Create a table that contains a row with a string for each of these pairs. Each string should be a sentence describing the siblings by their size.
Each sibling pair should appear only once in the output, and siblings should be listed in alphabetical order (e.g.
"barack plus clinton..."
instead of"clinton plus barack..."
), as follows:Hint: First, create a helper table containing each pair of siblings. This will make comparing the sizes of siblings when constructing the main table easier.
Hint: If you join a table with itself, use
AS
within theFROM
clause to give each table an alias.Hint: In order to concatenate two strings into one, use the
||
operator.
完成了 Q5 之后这一题就很简单了.
CREATE TABLE sentences AS
SELECT "The two siblings, " || dogone || " plus " || dogtwo || " have the same size: " || dogonesize
FROM siblings
WHERE dogonesize = dogtwosize AND dogone < dogtwo;