⻚页⾯面 / … / Prolog task due in course git repository by end of day on 7 Mar 2019
the making of phase 2 of Prolog task due in course git
repository by end of day on 7 Mar 2019
由 Robert Webber创建, 最后修改于⼆二⽉月 24, 2019 TOC For this document:
1) Increasing flexibility of tester.pl code
1.1) Cleaning up tester.pl code (test_nfa_match_helper)
2) Introducing the notion of scanner, token names, and labelled accepting states 2.1) scanner_to_nfa
2.2) test_nfa_match(TransformedString, FA, Matches)
2.3) accepting(NFA, PossibleFinish, Match)
3) PHASE 2 LAUNDRY LIST:
4) Hint on Using Prolog with Phase 1 of this assignment
1) Increasing flexibility of tester.pl code
In moving on to phase 2, I decided I wanted more flexibility in the predicates I am using for testing. Specifically, I wanted to specify which of the three assignment phases a test was with and how that phase gets tested and I also wanted to be able to control which test cases I was running (i.e., often I found myself wanting to ignore most of the test cases and just run one of them). So I want to be able to have tests that look like:
test_case(phase1, case01, “a”,letter concat (letter star), my_succeed).
test_case(phase1, case02, “a”,letter concat letter star, my_fail).
where I can specify which phase they are associated with and given them unique names if I want to test them individually. And then I want to be able to run queries like:
| ?- test_count_successful_tests(N). test_count_successful_tests(N).
N=2
(2 ms) yes
| ?- test_count_successful_tests(phase1, all, N). test_count_successful_tests(phase1, all, N).
N=2
(3 ms) yes
| ?- test_count_successful_tests(phase1, [case01], N). test_count_successful_tests(phase1, [case01], N).
N=1
(2 ms) yes
| ?- test_count_successful_tests(phase1, [case02], N). test_count_successful_tests(phase1, [case02], N).
N=1
(2 ms) yes
| ?- test_count_successful_tests(phase1, [case01, case02], N). test_count_successful_tests(phase1, [case01, case02], N).
N=2
(2 ms) yes | ?-
This works in a completely backward compatible way because prolog allows me to have predicates with the same name but different arity, and it just matches on the one that fits the shape it is trying to match. So, I just added the following code to tester.pl without having to revise the existing code there
test_count_successful_tests(Phase, Tests, N) :- setof(A, test_example_run_tests(Phas
test_example_run_tests(Phase, Tests, Status) :-
member(TestCase, Tests),
test_case(Phase, TestCase, InputString, RegularExpression, Result)
test_categorize(InputString, TransformedString),
test_run_case(Phase, Result, TransformedString, RegularExpression,
Status = [InputString, RegularExpression, Result].
test_example_run_tests(Phase, all, Status) :-
test_case(Phase, _, InputString, RegularExpression, Result),
test_categorize(InputString, TransformedString),
test_run_case(Phase, Result, TransformedString, RegularExpression,
Status = [InputString, RegularExpression, Result].
test_run_case(phase1, my_succeed, TransformedString, RegularExpression, FA) :-
regular_expression_to_nfa(RegularExpression, FA),
test_nfa_match(TransformedString, FA).
test_run_case(phase1, my_fail, TransformedString, RegularExpression, FA) :-
regular_expression_to_nfa(RegularExpression, FA),
\+ test_nfa_match(TransformedString, FA).
test_debug_run_tests(Phase, Tests, Status) :-
member(TestCase, Tests),
test_case(Phase, TestCase, InputString, RegularExpression, Result)
test_categorize(InputString, TransformedString),
test_run_case(Phase, Result, TransformedString, RegularExpression,
Status = [InputString, RegularExpression, TransformedString, FA, R
test_debug_run_tests(Phase, all, Status) :-
test_case(Phase, _, InputString, RegularExpression, Result),
test_categorize(InputString, TransformedString),
test_run_case(Phase, Result, TransformedString, RegularExpression,
Status = [InputString, RegularExpression, TransformedString, FA, R
test_case(phase1, case01, “a”,letter concat (letter star), my_succeed).
test_case(phase1, case02, “a”,letter concat letter star, my_fail).
From here, I still need to add the predicates that define how test_cases of phase2 are evaluated (and ultimately add in similiar definitions for phase 3).
To see what is going on here, lets look at the predicate test_example_run_tests. In the making of phase 1 of Prolog task due in course git repository by end of day on 7 Mar 2019 , it is defined as:
test_example_run_tests(Status) :-
test_case(InputString, RegularExpression, my_succeed),
Result = my_succeed,
regular_expression_to_nfa(RegularExpression, NFA),
test_categorize(InputString, TransformedString),
test_nfa_match(TransformedString, NFA),
Status = [InputString, RegularExpression, Result].
test_example_run_tests(Status) :-
test_case(InputString, RegularExpression, my_fail),
Result = my_fail,
regular_expression_to_nfa(RegularExpression, NFA),
test_categorize(InputString, TransformedString),
\+ test_nfa_match(TransformedString, NFA),
Status = [InputString, RegularExpression, Result].
Looking at this code we see two predicates that differ only by one line (and whether they are handling the my_succeed or my_fail case). To allow this to be general across assignment phases, I am going to extract that line that does regular_expression_to_nfa and the one that does test_nfa_match and put them in their own predicate, called test_run_case (also used by the new test_debug_run_tests). This gives us:
test_example_run_tests(Phase, Tests, Status) :-
member(TestCase, Tests),
test_case(Phase, TestCase, InputString, RegularExpression, Result)
test_categorize(InputString, TransformedString),
test_run_case(Phase, Result, TransformedString, RegularExpression,
Status = [InputString, RegularExpression, Result].
test_run_case(phase1, my_succeed, TransformedString, RegularExpression, FA) :-
regular_expression_to_nfa(RegularExpression, FA),
test_nfa_match(TransformedString, FA).
test_run_case(phase1, my_fail, TransformedString, RegularExpression, FA) :-
regular_expression_to_nfa(RegularExpression, FA),
\+ test_nfa_match(TransformedString, FA).
And then to handle the case where we are specifying all (rather than providing a list of test cases), I add the predicate definition:
test_example_run_tests(Phase, all, Status) :-
test_case(Phase, _, InputString, RegularExpression, Result),
test_categorize(InputString, TransformedString),
test_run_case(Phase, Result, TransformedString, RegularExpression,
Status = [InputString, RegularExpression, Result].
Note that since all is not a list, member will fail on it in the previous definition of test_exam_run_tests. Note also that this definition doesn’t care which value of Phase it is being used with, and so hopefully won’t have to be changed.
1.1) Cleaning up tester.pl code (test_nfa_match_helper) Looking at:
test_nfa_match_helper(String, nfa(X,Y,transitions(Transitions)), State) :-
epsilon_closure(State, nfa(X,Y,transitions(Transitions)), Closure),
member(NextState, Closure),
NextState \= State,
member(next(State, NextState, epsilon), Transitions),
test_nfa_match_helper(String, nfa(X,Y,transitions(Transitions)), NextState).
we see that string could match “” (the empty list) which is already handled in an earlier rule. To prevent potential extra backtracking because of redundant rules, have rewritten this to be:
test_nfa_match_helper([H|T], nfa(X,Y,transitions(Transitions)), State) :-
epsilon_closure(State, nfa(X,Y,transitions(Transitions)), Closure),
member(NextState, Closure),
NextState \= State,
member(next(State, NextState, epsilon), Transitions),
test_nfa_match_helper([H|T], nfa(X,Y,transitions(Transitions)), NextState).
2) Introducing the notion of scanner, token names, and labelled accepting states
A scanner handles multiple token types, each of which can be described by a regular expression. As noted in Re: Prolog task due in course git repository by end of day on 7 Mar 2019 , we are basically doing the work of Figure 1.12 in the textbook. An example of a test_case would be:
test_case(phase2, case03, “a”,[scanner(identifier, letter concat (letter star))], [i
This implies that when the NFA is constructed for this regular expression, we track information so we can look up the token type (in this case identifier) that is associated with this regular expression. The my_succeed becomes a list because it is possible that more than one accepting state might be reachable with different token labels. Of course this is silly redundancy with just one token type. Where it becomes interesting is a test case like:
test_case(phase2, case03, “a”,[scanner(identifier, letter concat (letter star)),
scanner(number, digit concat (digit star))], [identif
where we now need an NFA that can match either identifiers or numbers and we need to be able to tell the difference. To make all this work, we are going to need new versions of your phase 1 solution predicates (as well as new versions of my test_run_case predicate, which I will supply shortly).
2.1) scanner_to_nfa
The main new predicate you are defining for phase 2 is something that converts a list of scanner pairs into an nfa. The usage in tester.pl is:
test_run_case(phase2, [H|T], TransformedString, ScannerExpression, FA) :-
scanner_to_nfa(ScannerExpression, FA),
test_nfa_match(TransformedString, FA, [H|T]).
test_run_case(phase2, [], TransformedString, ScannerExpression, FA) :-
scanner_to_nfa(ScannerExpression, FA),
test_nfa_match(TransformedString, FA, []).
scanner_to_nfa produces an nfa just like regular_expression_to_nfa did in phase 1. The nfa we are trying to produce has the form shown in Fig 1.12 in textbook. We see there is something new going on here, which is rather than just having accepting states, the accepting states have labels. So, for example there might be an accepting state for an identifier and a separate accepting state indicating that an integer has been recognized. When we look at the complex term for an NFA, it has the form nfa(start(X),Y,transitions(Z)). My code looks at X and at Z, so they have to be set the way my code expects. However, my code doesn’t look directly at Y, and so the information you track in Y is up to you. In my phase 2 solution, I used the Y structure to keep track of the labels associated with accepting states, which is different than what my phase 1 solution used it for. Much of the phase 1 code is re-used in phase 2, but things can be structured so that this doesn’t create conflicts on how Y is being used in the two phases.
2.2) test_nfa_match(TransformedString, FA, Matches)
The phase 1 test_nfa_match checked a TransformedString against an FA. In phase 2, it isn’t enough to just match, one now has to match with the right list of labels. This is handled by:
test_nfa_match(String, nfa(start(State),X,Y), Matches) :-
setof(Match, test_nfa_match_helper(String, nfa(start(State),X,Y), State, Match)
sort(Matches, SortedMatches),
ActualMatches = SortedMatches.
test_nfa_match(String, nfa(start(State),X,Y), []) :-
\+ setof(Match, test_nfa_match_helper(String, nfa(start(State),X,Y), State, Mat
The new test_match_helper/4 returns not just whether a match occurred (via success or failure) but also indicates the label associated with the match on success. The first body clause of the first rule above is gathering up all the successful matches and producing the list ActualMatches. The second body clause is sorting the list that was in the test_case predicate so that you don’t have to remember to. The last clause then says a match is successful if and only if it finds all and no more labels that were specified to be matched on.
The second rule handles the empty list of Matches, which I use as a convention to specify that no matches were made. It turns out that setof fails when nothing is found, rather than setting an empty list, so in the body of this clause, the list produced is ignored and \+ is used to succeed only if the setof fails.
As an example of the use of the first rule, we can look at the test case
test_case(phase2, case06, “aa”, [scanner(identifier, letter plus),
scanner(evenid, (letter concat letter) plus)],
[identifier, evenid]).
where I have a label identifier for one or more letters and a label evenid for identifiers with an even length. When I try to match this against aa, I expect both labels to be returned – in phase 3, this will change.
2.3) accepting(NFA, PossibleFinish, Match)
So far you have seen references to the notion of the accepting states having labels, but there has been nothing where your code communicates those labels back to my code. The place this happens is in my test_match_helper/4 and your accepting/3 as illustrated in
test_nfa_match_helper(“”, NFA, State, Match) :- epsilon_closure(State, NFA, Closure)
member(PossibleFinish, Closure),
accepting(NFA, PossibleFinish, Match).
test_nfa_match_helper([H|T], nfa(X,Y, transitions(Transitions)), State, Match) :-
member(next(State, NextState, H), Transitions),
test_nfa_match_helper(T, nfa(X,Y, transitions(Transitions)), NextState, Match).
test_nfa_match_helper([H|T], nfa(X,Y,transitions(Transitions)), State, Match) :-
epsilon_closure(State, nfa(X,Y,transitions(Transitions)), Closure),
member(NextState, Closure),
NextState \= State,
member(next(State, NextState, epsilon), Transitions),
test_nfa_match_helper([H|T], nfa(X,Y,transitions(Transitions)), NextState, Matc
In the first rule, when we meet the end of the input string, we check to see if there are any accepting states in the epsilon closure of the state we ended up in. This is all the same as phase 1, except when we want to know not just that acceptance happened, but what was the label of the state where the match happened. To do this, there is a third parameter to accepting. The expectation is that your predicate accepting/3 will cause this parameter to be bound to the label of the
accepting state.. The references to Match in these three rules just ensure that once you have bound the value of match, it gets communicated back to test_nfa_match where it is collected by the setof clause.
3) PHASE 2 LAUNDRY LIST:
In phase 2 you define two new predicates that are used by my code in app/tester.pl:
scanner_to_nfa with 2 arguments discussed in Section 2.1 above
accepting with three arguments discussed in Section 2.3 above. Note that your accepting with two arguments from phase 1 continues to exist. when prolog is working with a rule set, it checks not just the predicate name, but also how many arguments it is using, so accepting/2 and accepting/3 are seen as completely different things.
4) Hint on Using Prolog with Phase 2 of this assignment
Phase 2 is very much an extension of phase 1. In my solution, scanner_to_nfa makes significant use of the existing regular_expression_to_nfa . accepting\3 was a minor modification of accepting\2 – when the nfa is built right, accepting is a quick check whose main purpose is to hide information about the middle parameter of the nfa structure from my testing code – so it is the prolog equivalent of an object-oriented getter method.
With regards to prolog builtins, I used less than I used in Phase 1 since I reused the Phase 1 code unchanged. Specifically Phase 2 did not require is, sort, or findall.
⽆无标签
采⽤用⼀一个授予Department of Computer Science, The University of Western Ontario的免费Atlassian Confluence Community License。今天评估Confluence。