CS131: Programming Languages
DIS 1D Week 3 Winter 2022
Office Hours:
Copyright By PowCoder代写 加微信 powcoder
Tuesday 8-9pm, Friday 9:30-10:30am Zoom Link on CCLE (Same as discussion)
Discussion Section: 1D, Fridays 2:00 – 3:50pm
Agenda • HW2 & Hint Code Walkthrough
Homework #2
Homework 2: Overview
• Deadline:Thursday,Jan.27
• Significantly more difficult than homework 1
• Main task: How to (naively) find a parse tree for a given sentence?
Grammar Recap
• Grammar defines a language – What strings are valid sentence
• Consists of: – Rules
– Symbols: terminal and non-terminal
• The rules are applied by replacing non-terminal symbols with right-hand side of the rule
Example Grammar:
EXPR -> NUM BINOP NUM EXPR -> NUM
BINOP -> +
BINOP -> –
NUM -> 0 NUM -> 1
Derivation
• One can find out if a sentence is valid by trying to derive it from the grammar
• Top-down, leftmost derivation:
– Begin with start symbol and keep trying different rules in order
– Replace the leftmost non-terminal symbol according to selected rule
• Example: Find a derivation of “1-0”
Example Grammar:
EXPR -> NUM BINOP NUM EXPR -> NUM
BINOP -> +
BINOP -> –
NUM -> 0 NUM -> 1
Example Grammar:
EXPR -> NUM BINOP NUM EXPR -> NUM
BINOP -> +
BINOP -> –
NUM -> 0 NUM -> 1
Current sentence:
NUM BINOP NUM 0 BINOP NUM NUM BINOP NUM 1 BINOP NUM
1 BINOP NUM
Derivation (1-0)
Applied rule:
EXPR -> NUM BINOP NUM NUM -> 0
BINOP -> +
BINOP -> – NUM -> 0
Derivation Tree / Parse Tree • The derivation we found is:
EXPR -> NUM BINOP NUM NUM -> 1
BINOP -> –
• Can be expressed as the tree on the right
• You need to implement similar process in the homework.
NUM BINOP NUM
• Convert grammar expression from homework 1 format
• Hint:Yoursolutiondoesnotneed to use pattern matching although the example does.
– As long as the behavior is the same, it is okay.
– Takes a non-terminal symbol, returns the list of associated rules
• Write a function parse_tree_leaves, that returns a list of leaves from left to right
– In the example below, parse_tree_leaves should return [“1”; “+”; “3”]
Node (Expr, [
Node (Term, [
Node (Num, [ Leaf “1”]) ]);
Node (Binop, [ Leaf “+”]); Node (Expr, [
Node (Term, [
Node (Num, [ Leaf “3”])
Term Num “+” Term
Problem 2 • Parse tree representation:
Node (Expr, [
Node (Term, [
Node (Num, [ Leaf “1”]) ]);
Node (Binop, [ Leaf “+”]); Node (Expr, [
Node (Term, [
Node (Num, [ Leaf “3”])
Term Num “+” Term
• Write a function make_matcher gram that returns a matcher for
the grammar gram
• Matcher tells us if some prefix of the input can be generated using
our grammar
– e.g. Using our awkish_grammar and input [“1”; “+”; “1”; “-”], we can match [“1”; “+”; “1”] (or simply [“1”])
– Note: We are not looking for the longest match, instead return the first valid match found
Problem 3: Acceptor
• The returned matcher is a function: – Takes an acceptor and input fragment
• Acceptor:takesthesuffix(what’sleft after derivation), and tells if the suffix is acceptable
– If acceptable, returns Some x – Otherwise, None
• Allow for additional control over matches
– e.g. Denying non-empty suffix to force full matching
let accept_all x = Some x
let accept_empty_suffix = function
| [] -> Some [] | _ -> None
matcher accept_all [“9”; “+”; “$”] (* returns Some [“+”; “$”] for
awksub grammar *)
– Matcher will backtrack to find other matching until an accepted match is found (or no acceptable match exists).
Matcher Example
• Example: Find a match for “1 + 0 + 1” using grammar below – Assuming matcher tries to apply rules from top to bottom
EXPR -> NUM BINOP NUM EXPR -> NUM BINOP EXPR EXPR -> NUM
BINOP -> +
BINOP -> – NUM -> 0 NUM -> 1
let accept_all x = Some x
let accept_empty_suffix = function
| [] -> Some [] | _ -> None
matcher accept_all [“1”; “+”; “0”; “+”; “1”]
(* This will return Some [“+”; “1”] *)
matcher accept_empty_suffix [“1”; “+”; “0”; “+”; “1”]
(* This will return Some [] *)
• Write a function make_parser gram that returns a parser for the
grammar gram.
• Parser differs from the previous matcher in two ways
– Doesn’t take an acceptor, and only allows full matching
– It returns parse tree instead of suffix (or whatever returned by the acceptor)
Old Homework Walkthrough
Old Homework 2
• An old version of the homework:
https://web.cs.ucla.edu/classes/winter22/cs131/hw/hw2-2006- 4.html
• Task: Build a pattern matcher for genetic sequences
• Genetic sequence consists of letters (nucleotides): A, G, C, T (adenine, guanine, cytosine, thymine)
– e.g. ATGCCAGATCATTGC…
• Patterns are similar to regular expressions:
– Frag [symbol list]: exact match on a series of nucleotides • e.g. Frag [C; T; G] matches input [C; T; G]
– Or [pattern list]: matches any rule within
• e.g. Or [Frag [C; T]; Frag [A; G]] matches input [C; T] and [A; G]
– List [pattern list]: concatenates multiple patterns
• e.g. List [Frag [A; G]; Or [Frag [C]; Frag [T]]] matches input [A; G; C] and [A; G; T]
make_matcher
• The hint code contains a make_matcher function, with similar functionality to the current homework
– make_matcher pattern returns a matcher function for pattern
– The matcher function takes a fragment (input sequence) and an acceptor
– If the matcher finds a prefix of the fragment that matches the pattern, and the acceptor accepts the remaining suffix, it will return Some suffix.
– Otherwise, the matcher will return None.
make_matcher
• What are the results of the following matchings?
let pattern = List [
Frag [A; T];
Or [Frag [C]; Frag [C; T]];
Or [Frag [T; A]; Frag[A; G]]
let accept_all x = Some x
let accept_empty = function
| [] -> Some []
| _ -> None
let match1 = make_matcher pattern [A; T; C; T; A; G] accept_all let match2 = make_matcher pattern [A; T; C; T; A; G] accept_empty
Try to tackle the problem step by step, in a functional way
• Create a most basic matcher
• Build more complicated matcher over simple ones – Concatenation: e.g. A, B => A+B
– Choice:e.g.A,B=>A|B
– Relies heavily on higher-order functions and currying
Basic Building Block: nucleotide
let match_nucleotide nt frag accept =
match frag with
| [] -> None
| n::tail -> if n = nt then accept tail else None
• match_necleotide nt creates a “matcher” that matches a single nucleotide nt
Concatenating Matchers
• Starting from basic case: concatenate two matchers
• Given 2 matchers, matcher1, matcher2, return a matcher that matches matcher1 and matcher2 in a row
– Key: Properly define a new acceptor for matcher1
• Try to think why it works.
– When in doubt, emulate the behavior by hand, using the definitions of matchers and acceptors
let append_matchers matcher1 matcher2 frag accept =
matcher1 frag (fun frag1 -> matcher2 frag1 accept)
Concatenating Matchers
• What if we want to concatenate a list of matchers into one?
– Use the append_matchers created before
– Divide and conquer: If the list is not empty, concatenate the first one and the one formed by recursively concatenating the rest
let rec append_matcher_list matcher_list frag accept = match matcher_list with
[] -> accept frag
| matcher1::rest ->
append_matchers matcher1 (append_matcher_list rest) frag accept
Concatenating Matchers
• With matcher concatenation implemented, we can already handle the “Frag” case
Matcher for Frag [A; T; C] append_matcher_list [match_nt A; match_nt T; match_nt C]
let match_frag l = append_matcher_list (List.map match_nucleotide l)
Concatenating Matchers (Hint Code)
• The hint code uses make_appended_matchers to create concatenated matchers from a list
– Observation: The list of matchers are created with the same function. Thus, it fuses matcher creation (mapping) into concatenation process.
make_appended_matchers
match_nucleotide
match_nucleotide A match_nucleotide T match_nucleotide C
The common matcher “creator”
let make_appended_matchers make_a_matcher ls =
let rec mams = function
| [] -> (fun frag accept -> accept frag) |head::tail->append_matchers (mamstail)
in mams ls
Matchers generated on the fly
(make_a_matcher head)
Currying in Matcher Concatenation
• Compare the original append_matcher_list and hint version of make_appended_matchers:
let rec append_matcher_list matcher_list frag accept =
match matcher_list with
[] -> accept frag
| matcher1::rest ->
append_matchers matcher1 (append_matcher_list rest) frag accept
let make_appended_matchers make_a_matcher = function
[] -> (fun frag accept -> accept frag)
| head::tail ->
append_matchers (make_a_matcher head)
(make_appended_matchers make_a_matcher tail)
Concatenating Matchers
• The matcher for List can also be constructed in the same fashion
– Suppose we already have the make_matcher function for arbitrary patterns
• The code:
make_matcher (Frag [C;G]) make_matcher (Or [Frag [T];
make_appended_matchers
make_matcher
[Frag [C;G];
Or [Frag [T]; Frag [A]]]
Frag [A]])
matches List [Frag [C; G]; Or [Frag [T]; Frag [A]]]
let rec make_matcher = function
| Frag frag -> make_appended_matchers match_nucleotide frag
| List pats -> make_appended_matchers make_matcher pats
| Or pats -> make_or_matcher make_matcher pats
Matching Or
• Or matching is simpler:
– Logic: Try the matchers one by one
– Note the similarities with make_appended_matchers: 1) matcher creation on the fly; 2) usage of currying
let rec make_or_matcher make_a_matcher = function
| [] -> (fun frag accept -> None)
| head::tail ->
match_none, the matcher that corresponds to Or []
let head_matcher = make_a_matcher head
and tail_matcher = make_or_matcher make_a_matcher tail
in fun frag accept ->
let ormatch = head_matcher frag accept
in match ormatch with
| None -> tail_matcher frag accept
| _ -> ormatch
Hints for Homework 2
• Consider the relationship between our “grammar” with nucleotide
– In what situation are you matching “x and y” vs. “x or y”.
– What’s the difference between our homework and the old version?
• Besides matcher, we also need to implement a parser tree builder – How to do that?
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com