Compiler Construction/Spring 2022 Homework 2
1 String Matching
Question 1.1 (3 points). Considering the alphabet Σ = {0, 1}, give a basic regular expression for each
of the following languages:
Copyright By PowCoder代写 加微信 powcoder
1. All strings that start and end with the same symbol. 2. All strings that have an odd length.
3. All strings that do not contain the substring 10.
1. 1(0|1)*1|0(0|1)*0
2. (0|1)((0|1)(0|1))*
Question 1.2 (3 points). Consider the following regular expression: a((b|c)d+)*
Give an NFA that accepts the same language.
Answer. One possible NFA (obtained by the automatic conversion discussed in class) is:
a // b **
1 2 443jj 4
Adapted from CSCI-GA.2130-001 assignments by and .
Page 1 of 5
Question 1.3 (6 points). Consider the following NFA:
ε ::1 x //2
Answer. This NFA accepts strings that are either sequences of ’y’s or sequences of two or more ‘x’es. Constructing the DFA yields:
x B C y$$ ss
Describe informally the strings accepted by this NFA. Give a DFA that accepts the same language.
–99 E x,y
Question 1.4 (6 points). Consider the following DFA: c
JJ 2 a,b,c
Give a regular expression that accepts the same language.
Answer. The regular expression can be constructed directly from the DFA: c∗b(a|c)∗(b(a|b|c)∗)? a(a|b|c)∗
The relationship is easier to see if the DFA is unfolded to a non-minimal variant:
c a,c start // b //
a b JJ2′ JJ2′′
a,b,c a,b,c
a,c start // b //
Adapted from CSCI-GA.2130-001 assignments by and .
Page 2 of 5
Question 2.1 (3 points). Investigate the documentation (https://jflex.de/manual.html) and
source code of JFlex (https://github.com/jflex-de/jflex) to answer the following questions: 1. What algorithm does JFlex use to construct the DFA?
2. What algorithm does JFlex use to minimize the DFA?
3. Using what pattern may greatly increase the number of DFA states?
1. JFlex constructs the DFA using the subset construction algorithm that we discussed in class:
https://github.com/jflex-de/jflex/blob/5abf9aa5ae558a8004bf643cb739e9d75ba4b45 7/jflex/src/main/java/jflex/dfa/DfaFactory.java#L21.
2. JFlex minimizes the DFA using Hopcroft’s algorithm (which we did not discuss): https://gith ub.com/jflex-de/jflex/blob/51fa83538946c85a8f2fd96a582ecc7c227ecaed/jflex/src/ main/java/jflex/dfa/DFA.java#L317.
3. Both the manual and source code (https://github.com/jflex-de/jflex/blob/733ee562244 c429e64abc5bca8e1cdd152d27e1c/jflex/src/main/java/jflex/core/NFA.java#L565) warn that using negation may lead to exponentially many states in the NFA-to-DFA conversion.
Question 2.2 (4 points). Study the JFlex manual (https://jflex.de/manual.html) and examples (https://github.com/jflex-de/jflex/tree/master/jflex/examples/) to familiarize yourself with JFlex, then write a JFlex program that transforms its input as follows:
• Directive setname
• Directive name is replaced with the previously set name.
Thus, your program should transform:
setname I met name. name lives nearby.
setname I met name. name lives nearby too.
into (what to leave in place of setname
Yesterday I met Alice. Alice lives nearby.
Today I met Bob. Bob lives nearby too.
Make sure to actually perform this exercise on a computer. Setting up a development environment where you can experiment with JFlex is part of the challenge and will serve you well in the project.
Adapted from CSCI-GA.2130-001 assignments by and . Page 3 of 5
%class Hw2
%standalone
String name;
^setname.+$ { name = yytext().substring(8); }
name { System.out.print(name); }
Question 2.3 (5 points). Write a JFlex program that transforms its input as follows:
• Directives beginnames and endnames delimit a section containing an arbitrary number of names. • Directive names is replaced with the names previously listed between beginnames and endnames.
Thus, your program should transform:
beginnames
Yesterday I met names. names live nearby.
into (the exact way of inserting and’s or other separators is not important):
Yesterday I met Alice and Bob and Chara. Alice and Bob and Chara live nearby.
Answer. We can implement the requested behavior by introducing a new lexical state (NAMES), which we enter on seeing beginnames and leave (returning to the original YYINITIAL state) on seeing endnames:
import java.util.ArrayList;
import java.util.List;
Adapted from CSCI-GA.2130-001 assignments by and . Page 4 of 5
%class Hw2
%standalone
List
%state NAMES
^beginnames$ { yybegin(NAMES); }
^endnames$
{ System.out.print(String.join(” and “, names)); }
{ yybegin(YYINITIAL); }
{ names.add(yytext()); }
Adapted from CSCI-GA.2130-001 assignments by and .
Page 5 of 5
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com