Trivial Prolog in Java

001: package ca.draisey.free.tprolog;
002:
003:
004:
005:
006:
007: // Trivial Prolog syntax in DCG
008: // -- specially designed to be easier to parse than the standard Edinburgh syntax --
009: //
010: //dictionary --> [':'], clause, [';'], dictionary.
011: //dictionary --> [].
012: //
013: //clause --> predicate, dclause.
014: //dclause --> ['.'], predicate, [','], dclause. // alternative 1
015: //dclause --> predicate, dclause.               // alternative 2
016: //dclause --> [].
017: //
018: //predicate --> atom, dpredicate.
019: //dpredicate --> ['('], term, [')'], dpredicate.
020: //dpredicate --> [].
021: //
022: //term --> ['['], term, [']'], term.
023: //term --> ['"'], dstring.                      // string literal "abc" == ['a']['b']['c']
024: //term --> [''''], [:NONQUOTE-CHAR:], [''''].   // character literal 'a' == a
025: //term --> function.
026: //term --> variable.
027: //term --> [].
028: //
029: //dstring --> ['"'].
030: //dstring --> [:NONQUOTE-CHAR:], ddstring.
031: //
032: //ddstring --> ['"'], term.
033: //ddstring --> [:NONQUOTE-CHAR:], ddstring.
034: //
035: //function --> atom, dfunction.
036: //dfunction --> ['('], term, [')'], dfunction.
037: //dfunction --> [].
038: //
039: //atom --> [:LOWERCASE-TOKEN:].
040: //
041: //variable --> [:UPPERCASE-TOKEN:].
042:
043: // a trivial example of the Trivial Prolog syntax
044: // : member( A )( [ A ]Z );
045: // : member( A )( [ Z ]B )  member( A )( B );
046:
047:
048:
049:
050:
051: // a simple top down parser
052: final class Parse {
053:         private Parse( final java.io.Reader rin )
054:         {
055:                 lex = new Lex( rin );
056:         }
057:         static Sentence goal( final java.io.Reader rin )
058:         {
059:                 try {
060:                         return new Parse( rin ).goalQuantified();
061:                 }
062:                 catch ( LexException x ) {
063:                         throw new IllegalArgumentException( "LexException " + x.getMessage() );
064:                 }
065:         }
066:         static void database( java.io.Reader rin, Consultable db )
067:         {
068:                 try {
069:                         new Parse( rin ).consultDictionary( db );
070:                 }
071:                 catch ( LexException x ) {
072:                         throw new IllegalArgumentException( "LexException " + x.getMessage() );
073:                 }
074:         }
075:
076:         // the whole file/dictionary parser
077:         private final void consultDictionary( Consultable db ) throws LexException
078:         {
079:                 db.abolishDatabase();
080:                 while( lex.popif( ':' ) ) {
081:                         final Sentence r = ruleQuantified();
082:                         lex.popso( ';' );
083:                         db.appendzDatabase( r );
084:                 }
085:         }
086:
087:         // the inner parser ParseQuantified assembles a symbol table of all variable
088:         // references seen during parsing and unifies identical variables down to a 
089:         // single QuanTerm object each.
090:         //
091:         // these two methodsare effectively "static" methods of the inner class ParseRule
092:         // and if the language had been designed properly that is where they would reside
093:         private Sentence ruleQuantified() throws LexException
094:         {
095:                 return new ParseQuantified().rule();                    
096:         }       
097:         private Sentence goalQuantified() throws LexException
098:         {
099:                 return new ParseQuantified().goal();                    
100:         }       
101:         private class ParseQuantified {
102:                 // the exported rule and goal parsers
103:                 final Sentence rule() throws LexException
104:                 {
105:                         final Clause c = clause();                      
106:                         return variables.quantify( c );
107:                 }
108:                 final Sentence goal() throws LexException
109:                 {
110:                         final Term t = predicate();
111:                         return variables.quantify( t );
112:                 }
113:                 
114:                 // the actual top down parser   
115:                 private final Clause clause() throws LexException
116:                 {
117:                         final Clause c1 = predicate();
118:                         return dclause( c1 );
119:                 }
120:                 private final Clause dclause( final Clause c1 ) throws LexException
121:                 {
122:                         if( lex.popif( '.' ) ) {
123:                                 final Clause c2 = new HornClause( c1, predicate() );
124:                                 lex.popso( ',' );
125:                                 return dclause( c2 );
126:                         }
127:                         else if( lex.peekatom() ) {
128:                                 final Clause c2 = new HornClause( c1, predicate() );
129:                                 return dclause( c2 );
130:                         }
131:                         else {
132:                                 return c1;
133:                         }
134:                 }
135:                 private final Term predicate() throws LexException
136:                 {
137:                         final Term p1 = atom();
138:                         return dpredicate( p1 );
139:                 }
140:                 private final Term dpredicate( final Term p1 ) throws LexException
141:                 {
142:                         if( lex.popif( '(' ) ) {
143:                                 final Term p2 = new PairTerm( p1, term() );
144:                                 lex.popso( ')' );
145:                                 return dpredicate( p2 );
146:                         }
147:                         else {
148:                                 return p1;
149:                         }
150:                 }
151:                 private final Term term() throws LexException
152:                 {
153:                         if( lex.popif( '[' ) ) {
154:                                 final Term p1 = term();
155:                                 lex.popso( ']' );
156:                                 final Term p2 = term();
157:                                 // return new PairTerm( new PairTerm( new AtomTerm( "cons" ), p1 ), p2 );
158:                                 return new ConsTerm( p1, p2 );
159:                         }
160:                         if( lex.popif( '"' ) ) {
161:                                 if( lex.popifqq() ) {
162:                                         return new AtomTerm( "null" );
163:                                 }
164:                                 else {
165:                                         Term p1 = new AtomTerm( lex.popnonqq() );
166:                                         Term p2 = ddstring();
167:                                         return new ConsTerm( p1, p2 );
168:                                 }
169:                         }
170:                         if( lex.popif( '\'' ) ) {
171:                                 Term a = new AtomTerm( lex.popnonqq() );
172:                                 lex.popso( '\'' );
173:                                 return a;
174:                         }
175:                         else if( lex.peekatom() ) {
176:                                 return function();
177:                         }
178:                         else if( lex.peekvariable() ) {
179:                                 return variable();
180:                         }
181:                         else {
182:                                 return new AtomTerm( "null" );
183:                         }
184:                 }
185:                 private final Term ddstring() throws LexException
186:                 {
187:                         if( lex.popifqq() ) {
188:                                 return term();
189:                         }
190:                         else {
191:                                 Term p1 = new AtomTerm( lex.popnonqq() );
192:                                 Term p2 = ddstring();
193:                                 return new ConsTerm( p1, p2 );
194:                         }
195:                 }
196:                 private final Term function() throws LexException
197:                 {
198:                         final Term p1 = atom();
199:                         return dfunction( p1 );
200:                 }
201:                 private final Term dfunction( final Term p1 ) throws LexException
202:                 {
203:                         if( lex.popif( '(' ) ) {
204:                                 Term p2 = new PairTerm( p1, term() );
205:                                 lex.popso( ')' );
206:                                 return dfunction( p2 );
207:                         }
208:                         else {
209:                                 return p1;
210:                         }
211:                 }
212:                 private final Term atom() throws LexException
213:                 {
214:                         return new AtomTerm( lex.popatom() );
215:                 }
216:                 private final Term variable() throws LexException
217:                 {
218:                         return variables.linkQuanTerm( lex.popvariable() );
219:                 }
220:
221:                 // the quantified variables for a given rule
222:                 private SymbolTable variables = new SymbolTable(); // final
223:         }
224:
225:         // the lexer for the whole dictionary
226:         private final Lex lex;
227: }
228:
229: // fin