页面 / … / Prolog task due in course git repository by end of day on 7 Mar 2019
the making of phase 1 of Prolog task due in course git repository by end of day on 7 Mar 2019
由 Robert Webber创建, 最后修改于昨天4:11 下午
Below I show the testing code for phase 1 of the prolog task. Like the Ruby assignment, my sample testing code is in app/tester.pl and your solution code is expected to be in lib/due190307.pl .
TOC For this document:
1)Running the assignment
2)Automating the testing of your prolog
3)New Regular Expression Notation
4)Phase 1 tester.pl code
4.1) Preliminary Comments on Task
4.2) The Testing Code
5)PHASE 1 LAUNDRY LIST:
6)Hint on Using Prolog with Phase 1 of this assignment
1) Running the assignment
Unlike Ruby, instead of running the testing code from the app directory, one brings together the testing and solution by typing:
which puts you in the prolog interpreter where you can explore your code. At the final stage of checking my phase 1 solution, a session with the interpreter might look like:
Sigh, for some reason I frequently forget how to exit prolog – it turns out if you hit cntrl-c twice it brings up the interruption prompt to which e will exit (and h will remind you when you forget e).
2) Automating the testing of your prolog
Of course, hopefully by now you know the benefits of being able to automate your testing rather than retype it over and over. The following works:
I found the following predicates useful while testing and so provide them to you:
· test_count_successful_tests(N) which tells you how many of your tests succeeded
· test_example_run_tests(Status) which shows you which tests succeeded
· test_debug_run_tests(Status) which shows you which tests succeeded and what the NFA was that you built as well as what the input string was transformed to (this latter being done by my provided code).
As with the Ruby code, I had to write something that would match a string against an NFA.
· test_nfa_match(String, nfa(start(State),X,Y)) matches a string against an NFA
· test_nfa_match_helper(String, nfa(start(State),X,Y), State) makes · · · test_nfa_match easier to write by adding a specification of which state to start the match from (so matching substrings is like matching the whole string, just with different starts)
· test_categorize converts strings to lists of categories
· test_category converts a character to a category
· test_category_helper converts all the characters to categories except those going to the category undefined (Z in the Ruby notation)
The actual test cases are presented like:
In the Ruby assignment, this would have been equivalent to:
In the test_case , my_fail is used when the match should fail and my_succeed is used when the match should succeed.
3) New Regular Expression Notation
You will notice that the regular expression notation has changed from the Ruby assignment. This is because Prolog handles the conversion from infix notation to a tree for us. Consider the following:
so, basically, using the ops directives in directives.pl (which are also in the provided tester.pl), when I type
prolog is automatically converting it into a tree notation of
The prolog tree notation looks a lot like the prefix lisp notation of the Ruby assignment except that the operator is just before the associated parenthesis contained parameters rather than being the first item in the parenthesis list. In prolog language this is a complex term. In our Ruby notation, . could take an unlimited number of parameters, but in our prolog notation being derived from infix, concat takes two parameters. However, prolog also handles associativity of binary operators so
You can use parenthesis as you normally would in the infix version and they will disappear in the complex term version (although they will have, in the process, guided the shape of the complex term).
The operators to be supported in the assignment are:
The leaves of our regular expressions in this assignment will be
Prolog’s operator notation takes care of creating trees for regular expressions for us, so phase 1 starts with considering how to convert a regular expression tree to an NFA. As with the ruby assignment, testing is done by seeing if the resulting NFAs except the same strings as the regular expressions would have.
4) Phase 1 tester.pl code
tester.pl contains:
4.1) Preliminary Comments on Task
As noted in Re: the making of phase 1 of Prolog task due in course git repository by end of day on 7 Mar 2019 ,
These were notes I wrote before doing the implementation and so have drifted a bit from the actual testing code, however, the nfa term still has three parts:
· The first part however, is not a State, but the term start(State) where State is filled in with the `name’ of the start state. This structure is used by my test_nfa_match predicate to find the start of the automata that is being matched against.
· The States list maps nicely to the book definition of an NFA. However, my testing code never checks directly to see what you put in there. Keeping a list of state(Name,Status) values there would work fine, but it is over- specification in the sense that you could store other structures there that could also work fine. The main thing is that somewhere there has to be the information that allows your accepting predicate to tell if a given state is an accepting state or not. And in phase 2 (and 3), for the accepting states, you also need to know what token type they are accepting.
· The transitions() structure matters and is used by test_nfa_match_helper to explore paths thru the nfa.
· As to the structure of a state name, all it has to be is something that = works with. In an instance of an nfa, I would expect it to be grounded, i.e., having no free variables.
4.2) The Testing Code
5) PHASE 1 LAUNDRY LIST:
what you are writing in due190307.pl for phase 1 is the definition of the predicates
6) Hint on Using Prolog with Phase 1 of this assignment
· The builtins are defined in http://www.gprolog.org/manual/gprolog.html . A lot of other stuff is in there too. Most of it bad for an assignment like this one, but useful for other more complicated tasks. Remember prolog is about separating logic from control and in this assignment there should be very little reason to specify control (hence most of the classic impure parts of prolog are not listed among the builtins above. But, as with the Ruby assignment, badly written code that follows the assignment restrictions and passes the test data will be marked as if it were well written code.
