Confluence
/ ! ” #
$
/… ⋆F &W ‘S (
/ Ruby task due in course git repository by end of day on 14 Feb 2019
The Making of Phase 2 of Ruby task due in course
git repository by end of day on 14 Feb 2019
Robert Webber 08 2019 thru April
Continuing from The Making of Phase 1 of Ruby task due in course git repository by end of day on 14 Feb 2019 created app/phase_2_sample_tests.rb
ory by enrdeqoufidraey_orne9laAtpirv2e01″9phase_1_helpers” require_relative “phase_2_helpers” require_relative “../lib/due190214”
n 2018 @total = 0 @pass = 0
! Course Announcements 2019 January 2019 Calendar
Discussion of Final Exam
Erlang task due in course git reposit Haskell task due in course git reposi
, How to use git
Keeping Up With The Wiki
, OLD Course Announcements from J
, Prolog task due in course git reposit
! Ruby task due in course git reposito
How to start a program
Ruby Task Laundry List
The Making of Phase 1 of Ruby ta The Making of Phase 2 of Ruby The Making of Phase 3 of Ruby ta
Software environment of CS3342 co
, Standard setup for course BitBucket
Warmup task due in course git repo
, Week 01: Jan 9 10 of 2019
, Week 02: Jan 16 17 of 2019
Week 03: Jan 23 24 of 2019
, Week 04: Jan 30 31 of 2019
, Week 05: Feb 6 7 of 2019
, Week 06: Feb 13 14 of 2019
, Ruby material Prolog Material Erlang Material
, Haskell Material
, Implementing Language Interpreters a
, Static Code Analysis and CASE Tools
, Misc
ry by end of day on 21 Mar 2019
ry by endeoff daasysoenrt7(Mmearss20ag19e, test) @total = @total + 1
y by end of day on 14 Feb 2019
if test then
@pass = @pass + 1
puts “success: ” + message
else
)
–
.
k due in course gpiuttrespo”sfiatoirlyebdy:en”d+ofmdeasysoang1e4 Feb 2019 end
ask due in course git repository by end of day on 14 Feb 2019
end
sk due in course git repository by end of day on 14 Feb 2019
@total = 0
mpute server used for marking
@pass = 0 repositories
test_case = “(.(|LD)D(|LD(.DQ)))” itory by end of day on 24 Jan 2019
test_case_tree = PrefixToTree.new(test_case).to_tree assert(“can handle (.(|LD)D(|LD(.DQ)))”,
TreeHolder.new(test_case_tree).to_s == test_case)
test_case = “(+D)”
target = “111”
test_case_tree = PrefixToTree.new(test_case).to_tree test_case_nfa = TreeToNFA.new(test_case_tree).to_nfa assert(“NFA can match 111 against (+D)”,
NFAScanner.new(test_case_nfa).match(target))
puts @pass.to_s + ” passed out of ” + @total.to_s + ” tests.”
Which shows how the second piece of this assignment will be tested. Note that the assert
method from phase_1_sample_tests.rb has also been changed so that like the one above it
prints a message on both failure of the assertion and on success which helps to figure out d Compilers
which test threw an exception – which shouldn’t happen in working code.
Again we make use of your PrefixToTree class from the first phase. However now we are also using a TreeToNFA class that you have to write for this phase. The TreeToNFA class supports new and to_nfa . The question again arises of how to test that the NFA produced is correct. The approach taken here is to use it to try and see if various regular expressions match various strings. This is done by a class NFAScanner which I write in app/phase_2_helpers.rb. The implementation of NFAScanner provided imposes further constraints on how TreeToNFA works. NFAScanner looks like:
class String def category
return “L” if self =~ /[a-zA-Z]/ return “D” if self =~ /[0-9]/ return “Q” if self == “?”
return “E” if self == “!”
return “P” if self == “.”
return “C” if self == “,”
return “K” if self == “:”
return “M” if self == “-”
return “A” if self == “+”
return “B” if self =~ /[\*\/\%\^]/ return “X” if self == “(”
return “Y” if self == “)” return “S” if self == “=” return “T” if self == “<" return "U" if self == ">” “Z”
end end
class NFAScanner
def initialize(nfa)
@nfa = nfa end
def match(string)
state = @nfa.start
match_helper(state, string)
end
private
def match_helper(state, string)
current_states = [ state ] + @nfa.epsilon_closure(state) return accepting?(current_states) if string.empty? next_states = move_forward(string[0].category, current_states) return false if next_states.empty? match_helper_try(next_states, string[1..-1])
end
def accepting?(states)
states.any? { | state | state.accepting? }
end
def move_forward(category, states)
forward = []
states.each do | state |
forward = forward + @nfa.next(state,category)
end
forward end
def match_helper_try(states, string) states.any? do | state |
match_helper(state, string)
end
end end
Looking at the code to NFAScanner we find that the object to_nfa returns must meet the requirements:
S. an NFA accepts message start and returns something I will refer to as a state see method match
T. an NFA accepts message epsilon_closure with parameter state and returns something I will call states that can be concatenated with an Array see method match_helper. epsilon_closure is defined in Def 1.2 on page 13 of the textbook. you will find it is also useful for phase 3 of this assignment.
W. states must accept the any? message see method accepting?
Y. a state must accept the accepting? message see method accepting?
Z. an NFA accepts the message next with parameters state and category to return
something that can be concatenated with an Array states see method move_forward
In addition to this `type information’ there is the overall semantic constraint that if these various messages are implemented correctly then the match method in my NFAScanner class should be able to correctly determine from the NFA whether or not the NFA would match a particular string with the answer being the same as would be expected from the question of whether or not the original regular expression would match that same string.
As with the first phase the test data that will be used to evaluate the correctness of your solution will not be limited to that that appears in app/phase_2_sample_tests.rb .
* + 42
Haolun Li Professor
I’m just trying to get a handle of the second Ruby task and I ran into this error: undefined method `accepting?’ for “nextinput1 input2”
This is a little confusing to me and I can’t seem to turn up anything about it by searching online. Is the method next suppose to contain a listening inside called ‘accepting?’?
03 2019
Robert Webber
It would be more useful if you cut and paste in the actual error message than summarize it as you appear to have above. As you might expect undefined method means someone is sending a message to an object that doesn’t know how to handle that message. There are at least two accepting? s floating around the system one mentioned in item 4 above which you would have to define in your code and the other I defined in the class for NFAScanner which in turn references the item 4 accepting? .
03 2019 Haolun Li
Traceback most recent call last:
6: from app_frank/phase_2_sample_tests.rb:30:in `
5: from C:/Users/Frank/Dropbox/Frank Folder/Western/2018 – 2019/2018 B Fall Term/CS3342 languages/hli843/assignments/due190214/app_frank/phase_2_helper s.rb:78:in `match’
4: from C:/Users/Frank/Dropbox/Frank Folder/Western/2018 – 2019/2018 B Fall Term/CS3342 languages/hli843/assignments/due190214/app_frank/phase_2_helper s.rb:86:in `match_helper’
3: from C:/Users/Frank/Dropbox/Frank Folder/Western/2018 – 2019/2018 B Fall Term/CS3342 languages/hli843/assignments/due190214/app_frank/phase_2_helper s.rb:95:in `move_forward’
2: from C:/Users/Frank/Dropbox/Frank Folder/Western/2018 – 2019/2018 B Fall Term/CS3342 languages/hli843/assignments/due190214/app_frank/phase_2_helper s.rb:95:in `each’
1: from C:/Users/Frank/Dropbox/Frank Folder/Western/2018 – 2019/2018 B Fall Term/CS3342 languages/hli843/assignments/due190214/app_frank/phase_2_helper s.rb:96:in `block in move_forward’
C:/Users/Frank/Dropbox/Frank Folder/Western/2018 – 2019/2018 B Fall Term/CS3342 languages/hli843/assignments/due190214/app_frank/phase_2_helper s.rb:96:in `+’: no implicit conversion of nil into Array TypeError
03 2019 Haolun Li
Professor Webber
Thanks for getting back to me. I was wondering if could help me find more documentation on the how accepting?s work in Ruby. If I find a couple examples the it would really help me understand what I need to do.
Appreciate your help Frank
03 2019
Robert Webber
accepting? is a term from the application domain. It is a message being sent to a state. If you refer to the textbook discussion of finite automata you will find that some states are accepting and some aren’t. Hence the name. The question mark is a common convention in Ruby to indicate that a method is boolean i.e. returns true or false as discussed in class and as appears as one of the posted exam questions on the Ruby material. Figuring out what things mean from context is an important part of reading and understanding already existing code which in turn is a major part of what programmers actually do for a living
03 2019
Robert Webber
It is useful to think of the code you are writing and that I wrote as a translation of the material on lexical analysis from the text. The code I wrote on NFAScanner translates the discussion of how a nondeterministic finite state machine is used to match on an input string to determine if the string is part of a language specified by a regular expression. The code you are writing in TreeToNFA is a translation of the discussion of how a regular expression is mapped to a corresponding NFA that NFAScanner can then use to match on an input string to see if the original regular expression would have matched that string. There is a lot of shared vocabulary between these two parts of the textbook discussion. The translation of some of the very basic terms such as state I have left for your side of the task with the constraint that they have to be defined so that the entire discussion fits together and works as expected.
03 2019 Robert Webber
The trace stuff is just telling you how you got to the place where the problem arose in terms of nesting of message passing. That is the trace doesn’t show the action that was taken just before the problem but instead shows who had the problem and who had asked them to do something that caused the problem back to the start of everything.
The problem indicated here is that on line 96 something is being `added’ to an array. Addition on an array is basically concatenating together two arrays. However rather than sending it an array you have sent it nil. Since nil is not an array and there is no magic way implicit conversion to convert it to an array the program broke an the exception you see above was thrown/ raised.
03 2019 Carolyn Owen
Hello
I have my Phase 1 working as expected but now unfortunately I’m still having trouble with the operators exact meaning in relation to the NFAs. I feel like I’m just not understanding what is meant by the . and + operators in relation to the subtrees that they have. Is there any way that I could get clarification again? I appreciate all of the help that you’ve tried to give already.
Thanks Carolyn
Logan Mitchell Gunn 07 2019 Robert Webber
In my recent response Re: Ruby task due in course git repository by end of day on 14 Feb 2019 I give the example:
For example the concatenation of n character classes should match only strings of length n where those classes line up for example .LDLDLD should only match inputs that are 6 characters long that are alternating letters and digits. Note that A1A2A3 and B3C1D2 both fit this pattern but they look identical when sent to your code as my matching program has already converted them to LDLDLD .
does that make sense? is there anything else about concatenation . that you were wondering about? Note in this example each L and D in the regular expression is a subtree and could be replaced by some other subtree to represent a different regular expression.
08 2019 Carolyn Owen
Ok I see now. That makes perfect sense using that example. Thank you again for clarifying.
09 2019 Robert Webber
With regards to the + operator your textbook introduces it at the bottom of page 4. It introduces the * operator at the bottom of Figure 1.1 . However the notion that * is more primitive than + is arbitrary – similar to whether while or until loops are primitive when you also have if statements analogous to | in regular expressions. Thus the discussion of * in the text and in Working out a lexical analysis example can be viewed as also talking about + . For example The Making of Phase 1 of Ruby task due in course git repository by end of day on 14 Feb 2019 starts by observing that the lexical analysis example
[a-zA-Z][a-zA-Z0-9]*
in the assignment notation would be written as
(.L(|e(+(|LD))))
Perhaps it would be worth noting that in the hypothetical not true situation where the assignment had had an * operator for 0 or more copies of the first subtree then the lexical analysis example would have been written as
(.L(*(|LD)))
While there is no * in your assignment perhaps considering how it would have connected to the text might help with seeing how + works.
08 2019 Xiaoou Li
Hi sir
I am just not understand the meaning of e which represents epsilon and why a-
zA-Za-zA-Z0-9* does not convert to .L|LD 09 2019
Xiaoou Li
and why does nextstatecategory require parameter “category”?
In the other word how can we use this category ? 09 2019
Robert Webber
To simplify the assignment I left out the square bracket notation for ranges of characters. I replaced it with uppercase letters corresponding to various standard ranges of characters. So instead of you having to figure out how to create edges for each of the 52 characters represented by
[a-zA-Z]
I just use the letter L as a standin and you can create a single edge for L. However my test strings look like normal text and include stuff like aXyu . I convert it to LLLL before passing it on to you. As a result you never have a reason to use my category method. See the code of NFAScanner for more details on what is happening.
09 2019 Robert Webber
By the way there is a lot of discussion in the textbook chapter on what is going on here. Where the textbook is using the term `transition’ I have chosen to use the shorter term `next’. The textbook also sometimes uses next this way but as next is a more generic English word it is sometimes used in the text for other things like `next character in a string’ whereas transition is always referring to the transition from one state to another. These sorts of vocabulary issues raise interesting issues when reading other people’s code – but they are the norm and so are something you have to deal with rather than expecting that other people will not do this sort of thing. You should expect them to be even worse when working with professional software which contains names created by various people at various times.
09 2019 Xiaoou Li
I really do not understand how NFA works can you give me an example or graph.
what is the NFA of this tree . L|
e+ |
LD
Did you read the chapter and Working out a lexical analysis example ? They contain many examples. In their notation your example would be written
L(e|((L|D)+)
where e is epsilon
L is [a-zA-Z]
D is [0-9]
which is very close to the example in Working out a lexical analysis example . Note L|D is the same thing as
[a-zA-Z] | [0-9]
which is the same thing as
[a-zA-Z0-9]
09 2019 Robert Webber
Epsilon is discussed in the chapter on lexical analysis and used in the regular expression notation they use there. They use a greek script lower case e for epsilon in the textbook and I have decided to use a regular latin typescript lower case e in the assignment notation. There is actually quite a bit of discussion of epsilon in that chapter.
Your example .L|LD would translate back into the book notation as [a-zA-Z][a-zA-Z0-9]
without the star operator. This would just match identifiers that were two characters long.
09 2019 Hao Ming Wang
Hi professor I read the bit on epsilon closure in the textbook and just wanted to make sure that I’m understanding it correctly. If we had this NFA shown in Fig 1.5 in the textbook sorry I wasn’t able to include the image then the function nfa.epsilon_closurestate5 would return state 6 and state 7 – is that correct?
09 2019
Robert Webber
Yes that is correct. 09 2019
Lionel Wesley Foxcroft Hi professor
What does the `any?` message do? My code passes all the tests you provided and all the variants of those I could think of but I never implemented a method like that so I don’t really know what’s going on there.
Thanks
09 2019
Robert Webber
Its a Ruby builtin for Arrays and other Enumerables see https://ruby- doc.org/core-2.4.0/Enumerable.html#method-i-any-3F . You also might find https://medium.com/yello-offline/ruby-the-enumerable-module-under- the-hood-some-caveats-f640ce39a07d interesting.
09 2019 Mitchell James Craig
I have read the text book definition of epsilon closure and am still a little confused. So epsilon closure given a state would return any other states which can be reached from the given state using only epsilon transitions? I just want to make sure I am understanding this correctly.
Thanks in advance
10 2019
Robert Webber
And the state itself also.
10 2019 Xiaoou Li
in phase 2 and 3 can we use some kinds of Search Tree algorithm instead of NFA or DFA?
10 2019
Robert Webber
Your phase 2 and 3 have to work from my NFAScanner and DFAScanner codes which send queries to parts of an NFA and a DFA respectively. If you were writing match from scratch I could see how matching from just the regular expression tree is a slow but possible approach but in order to integrate with my NFAScanner and DFAScanner code I don’t see where anything would be gained by not actually building the automata. However as I have pointed out Ruby is a duck typing
language https://en.wikipedia.org/wiki/Duck_typing and so as long as things behave as expected by NFAScanner and DFAScanner the implementation details are pretty much left up to you with some general constraints listed on the Ruby task due in course git repository by end of day on 14 Feb
2019 page.
10 2019 John Taylor Jewell
A graph data structure seems like a reasonable abstraction for the NFA. However it isn’t explicitly mentioned in the textbook or in the assignment instructions. Am I on the right path by implementing some sort of graph for the NFA or is this overcomplicating things? Thanks!
10 2019
Robert Webber
The formal definition of an NFA in the text talks about sets of states and transitions. The formal definition of a graph would look much the
same https://en.wikipedia.org/wiki/Graph_discrete_mathematics .
10 2019 Xiaoou Li
What type of data we should put in variable state? integer number or the node of tree
10 2019
Robert Webber
That is left up to you so long as NFAScanner and DFAScanner work as required.
10 2019 Xiaoou Li
so can I use some kinds of search tree method instead of NFA or DFA?
10 2019
Lionel Wesley Foxcroft
If it works ̄\__/ ̄ 10 2019
Robert Webber
Re: The Making of Phase 2 of Ruby task due in course git
repository by end of day on 14 Feb 2019
10 2019 Carolyn Owen
Just to make sure that I’m clear the next method does not include the epsilon_transition off of the give state correct?
10 2019
Robert Webber
Referring to the code above the next method nextstatecategory responds to a state and a category. The category comes
from move_forward(string[0].category, current_states) .
You can use irb to find out that the class of the result of indexing into a String is another String (rather than some sort of character class). When we look at the definition of category under the class String above (a classic example of the controversial practice of monkey patching https://en.wikipedia.org/wiki/Monkey_patch ), it never returns the e that would represent epsilon. So if next included epsilon transitions, they would never be used. Looking above the invocation of move_forward, we see current_states = [ state ]
+ @nfa.epsilon_closure(state) which handles the epsilon
transitions separately as a special case. I could have
taken either approach, but at the time I took the approach
above, and this now becomes part of the requirement that
your code has to work with my code.
10 2019 Robert Webber
Note: my tests are all about using different properly constructed regular expressions and strings through the top level interfaces defined in the helper files. I am not specifically unit testing your methods to see if they do anything in particular. I am testing the overall process to see if it does what it should. There is certainly room for doing inefficient things and hard to read things that I would mark down if I was individually marking by hand. There is also room for doing things that I did not anticipate but work out perfectly fine or even better in some sense than what I expect. However with 180+/- students I am not reading your code to decide if I think it was well done or not.
The standard TA contract is 140 hours per semester
https://grad.uwo.ca/finances/western_funding/gta/index.html . With 180 students this would mean 46 minutes per student per semester. Best practices on reading code in an environment where you are familiar with what is going on are https://smartbear.com/learn/code-review/best- practices-for-peer-code-review/ :
quote: In practice a review of 200-400 LOC over 60 to 90 minutes should yield 70-90% defect discovery. So if 10 defects existed in the code a properly conducted review would find between seven and nine of them.
So for the most part at university in courses with the enrollments that we are seeing your code is never really being read. This is true not just of large undergraduate classes but even of focused graduate research. Some people test code as I do but my understanding is that that is not the common case. Of course it turns out that code review when there are the resources to do it properly is better than testing
cf. https://kev.inburke.com/kevin/the-best-ways-to-find-bugs-in-your- code/ . However in the absence of proper resources testing scales up more efficiently. And we are usually in the absence of proper resources — indeed the underlying theme of the computer industry since World War II has been https://goleansixsigma.com/theres-never-enough-time-to-do-it- right-but-theres-always-enough-time-to-do-it-over/ .
The best way to get feedback on whether your code is readable is to participate in open source projects where there is someone `responsible’ for the project that accepts changes submitted by others via pull
requests https://github.com/features/code-review/ . Since the one responsible doesn’t know if the person submitting the change will be around to fix any problems with it such changes generally get a good review before being accepted.
10 2019 Carolyn Owen
I keep coming across the same bug and can’t seem to locate the origin to the problem. Is anyone else having trouble with the next method being passed a series of nodes correctly and then being passed an empty array as the last element? If not I’ll have to look back in my code again to see where I am creating the weirdness.
Thanks!
11 2019 Carolyn Owen
In case anyone is reading this later it turned out to be a problem with my return from epsilon_closure and trying to append a recursive call of the method.
11 2019
Robert Webber
glad to hear you found it. we will be doing a lot of recursion this semester as the intro to prolog today indicated. generally recursions fall into two categories those that are recursing on a part of their parameter in which case the important thing is to always be shrinking that parameter. The other are those that are growing something in which case the important thing is that with each call the thing being built gets larger and that ultimately you are building something that is finite. basically recursion and while loops are the same but with while loops you destroy your start with each iteration so in the end you only have the latest version and with recursion you destroy your work and only keep what is being returned which then gets used with previous versions.
5 Haolun Li
Hey everyone
Hope your assignment is going well. I was fortunate enough to get the help from Lionel a classmate of ours and with his permission I’m posting the test cases he built. You can find the Gitlab repo below. For those of you who aren’t familiar Gitlab is just a place where we can put files for people to download. There will be more detailed instruction in the link below:
This is viewed as unacceptable collaboration the repo has been taken down.
Also join the Facebook study group for the class. We can help each other:
https://m.me/join/AbZI0z50YtNg3ulo
Let’s make sure not to send each other code and instead focus on deciphering what exactly we are supposed to do.
5 Robert Webber
as per: Re: Ruby task due in course git repository by end of day on 14 Feb 2019
Why would you be doing it on Facebook rather than on the wiki? Other than creating an unfair advantage for some people rather than others?
And why would you think making up test data for you isn’t as much doing your work for you as writing code for you is? As discussed in Week 01: Jan 9 10 of 2019 the mark is supposed to represent your work not what you can do when a bunch of people help you. Posting questions to the wiki is the only exception I have approved – see discussion of `unacceptable collaboration’
in http://www.csd.uwo.ca/current_students/undergraduate_students/scholas tic_offences.html .
Xiaoxuan Yang 5 Hazem Moharram
For this part of the assignment I think there is an error in the way you test our code in phase_2_helpers.rb I might be wrong
In phase_2_sample_tests.rb if we set test_case = “|D|Q|LD” and set target = “a” The testing code can’t see that this test case matches the target. Can you confirm this through testing you’re on code to solve this assignment? It might be my own mistake of course but just to make sure as I’m having trouble spotting the error.
Thanks for your help.
EDIT: nvm this was my mistake
2 …
09 2019
Robert Webber
Department of Computer Science The University of Western OntarioAtlassian Confluence Community LicenseConfluence
Atlassian Confluence 6.13.0 Atlassian
o t
a o r
s
t
s
n