[SOLVED] prolog / / Prolog task due in course git repository by end of day on 7 Mar 2019

/ / Prolog task due in course git repository by end of day on 7 Mar 2019
the making of phase 3 of Prolog task due in course git
repository by end of day on 7 Mar 2019
Robert Webber, 8:45
TOC:
1) A DFA is an NFA that
1.1) Handling Conflicts with Accepting States 2) Laundry List for Phase 3
3) Hints for Phase 3
1) A DFA is an NFA that
A DFA is an NFA without epsilon transitions or multiple next links on the same input value (from the same state). So the tester just has to ask you to convert the NFA to a DFA
test_run_case(phase3, [H|T], TransformedString, ScannerExpression, DFA) :-
scanner_to_nfa(ScannerExpression, NFA),
scanner_nfa_to_dfa(NFA, DFA),
test_dfa_match(TransformedString, DFA, [H|T]).
test_run_case(phase3, [], TransformedString, ScannerExpression, DFA) :-
scanner_to_nfa(ScannerExpression, NFA),
scanner_nfa_to_dfa(NFA, DFA),
test_dfa_match(TransformedString, DFA, []).
with the predicate scanner_nfa_to_dfa and then do the match using my supplied test_dfa_match . It is in my test_dfa_match where I avoid epsilon closures and make sure that only one label is returned and that only one next matches a given state and input. test_dfa_match itself makes sure I didnt accidentally specify more than one label for the match
test_dfa_match(String, nfa(start(State),X,Y), Matches) :-
length(Matches, 1),
setof(Match, test_dfa_match_helper(String, nfa(start(State),X,Y), State, Match)
sort(Matches, SortedMatches),
ActualMatches = SortedMatches.
test_dfa_match(String, nfa(start(State),X,Y), []) :-
+ setof(Match, test_dfa_match_helper(String, nfa(start(State),X,Y), State, Mat

and test_dfa_match_helper
test_dfa_match_helper(, NFA, State, Match) :-
accepting(NFA, State, Match).
test_dfa_match_helper([H|T], nfa(X,Y,transitions(Transitions)), State, Match) :-
setof(NextState, member(next(State, NextState, H), Transitions), [NS]),
test_dfa_match_helper(T, nfa(X,Y, transitions(Transitions)), NS, Match).
makes sure there is only one next state NS on a given input. It also reuses the phase2 accepting predicate since a DFA is an NFA, accepting for a DFA should be the same as accepting for an NFA (except it never returns more than one label).
1.1) Handling Conflicts with Accepting States
A scanner gives us multiple pairs of regular expressions and token types associated with those expressions. The pairs come in order. When more than one pair could match the input, the token type for the first one is the one that is used and the other is ignored. Thus the test datum
test_case(phase3, case07, aa, [scanner(identifier, letter plus),
scanner(evenid, (letter concat letter) plus)],
[identifier]).
always returns identifier, because identifier is defined before evenid and anything that is an evenid would also be an identifier. On the other hand, the test datum
test_case(phase3, case07, aa, [scanner(evenid, (letter concat letter) plus)],
scanner(identifier, letter plus),
[identifier]).
would return evenid for aa and aaaa, but return identifier for a and aaa.
How you figure out the order of the pairs from the nfa that your phase 2 scanner_to_nfa built would depend on how you wrote it. It is possible you might want to rewrite it to make this determination easier while still meeting its phase 2 requirements.
2) Laundry List for Phase 3
For phase 3, the only thing new you have to write is scanner_nfa_to_dfa as described above.
3) Hints for Phase 3
You can think of phase 3 as having 2 subphases, one where the scanner has no conflicting accepting states and one where it does.
I dont expect to need any more prolog features than those I used in phase 1 and 2, but havent yet started on phase 3. The tester for phase 3 was sanity checked by giving it a hand coded nfa to see if it did the right thing, which it did.

Department of Computer Science, The University of Western OntarioAtlassian Confluence Community LicenseConfluence