001: /*
002: * $Id: LogikusParser.java,v 1.1 2003/08/19 01:12:57 jonesde Exp $
003: *
004: * Copyright (c) 1999 Steven J. Metsker.
005: * Copyright (c) 2001 The Open For Business Project - www.ofbiz.org
006: *
007: * Permission is hereby granted, free of charge, to any person obtaining a
008: * copy of this software and associated documentation files (the "Software"),
009: * to deal in the Software without restriction, including without limitation
010: * the rights to use, copy, modify, merge, publish, distribute, sublicense,
011: * and/or sell copies of the Software, and to permit persons to whom the
012: * Software is furnished to do so, subject to the following conditions:
013: *
014: * The above copyright notice and this permission notice shall be included
015: * in all copies or substantial portions of the Software.
016: *
017: * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
018: * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
019: * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
020: * IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
021: * CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT
022: * OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR
023: * THE USE OR OTHER DEALINGS IN THE SOFTWARE.
024: */
025:
026: package org.ofbiz.rules.logikus;
027:
028: import org.ofbiz.rules.parse.*;
029: import org.ofbiz.rules.parse.tokens.*;
030:
031: /**
032: * <p>This class provides a parser for Logikus, a logic
033: * language similar to Prolog.
034: * <p>The grammar this class supports is:
035: * <blockquote><pre>
036: *
037: * <old> <!-- note: this is the original grammar, see the current one below -->
038: * structure = functor ('(' commaList(term) ')' | Empty);
039: * functor = '.' | LowercaseWord | QuotedString;
040: * term = structure | Num | list | variable;
041: * variable = UppercaseWord | '_';
042: * factor = '(' expression ')' | Num | variable;
043: * </old>
044: *
045: * axiom = structure (ruleDef | Empty);
046: * structure = functor ('(' commaList(term) ')');
047: * functor = '.' | LowercaseWord | UppercaseWord;
048: * term = structure | Num | QuotedString | list | variable;
049: * variable = LowercaseWord | UppercaseWord | '_';
050: * <br>
051: * ruleDef = ":-" commaList(condition);
052: * condition = structure | not | evaluation | comparison | list;
053: * <br>
054: * not = "not" structure ;
055: * <br>
056: * evaluation = '#' '(' arg ',' arg ')';
057: * comparison = operator '(' arg ',' arg ')';
058: * arg = expression | functor;
059: * operator = '<' | '>' | '=' | "<=" | ">=" | "!=" ;
060: * expression = phrase ('+' phrase | '-' phrase)*;
061: * phrase = factor ('*' factor | '/' factor)*;
062: * factor = '(' expression ')' | Num | QuotedString | variable;
063: * <br>
064: * list = '[' (listContents | Empty) ']';
065: * listContents = commaList(term) listTail;
066: * listTail = ('|' (variable | list)) | Empty;
067: * <br>
068: * commaList(p) = p (',' p)*;
069: * </pre></blockquote>
070: *
071: * The following program and query use most of the features of
072: * the Logikus grammar:
073: *
074: * <blockquote><pre>
075: * // program
076: * member(X, [X | Rest]);
077: * member(X, [Y | Rest]) :- member(X, Rest);
078: * primes([2, 3, 5, 7, 11, 13]);
079: * factor(X, P, Q) :-
080: * primes(Primes),
081: * member(P, Primes), member(Q, Primes), =(P*Q, X);
082: * <br>
083: * // query
084: * factor(91, A, B)
085: * <br>
086: * // results
087: * A = 7.0, B = 13.0
088: * A = 13.0, B = 7.0
089: * no
090: * </pre></blockquote>
091: *
092: * The class <code>LogikusFacade</code> simplifies the
093: * construction of <code>Program</code> and <code>Query</code>
094: * objects from the text given above. A Java program can prove
095: * the query to generate the results.
096: *
097: * <p>
098: * The class <code>LogikusIde</code> is an example of using the
099: * <code>Logikus</code> parser in practice. It uses
100: * <code>LogikusFacade</code> to create a <code>Query</code>,
101: * proves the query, and displays the query's variables for
102: * each proof. As in Prolog, the Logikus development
103: * environment prints "no" when no further proofs remain.
104: *
105: * @author Steven J. Metsker
106: * @version 1.0
107: */
108: public class LogikusParser {
109: protected Sequence structure;
110: protected Sequence expression;
111: protected Sequence list;
112:
113: /**
114: * Return a parser that recognizes the grammar:
115: *
116: * arg = expression | functor;
117: */
118: protected Parser arg() {
119: Alternation a = new Alternation();
120:
121: a.add(expression());
122: a.add(functor().setAssembler(new AtomAssembler()));
123: return a;
124: }
125:
126: /**
127: * Return a parser that recognizes the grammar:
128: *
129: * <blockquote><pre>
130: * axiom = structure (ruleDef | Empty);
131: * </pre></blockquote>
132: *
133: * @return a parser that recognizes an axiom
134: */
135: public Parser axiom() {
136: Sequence s = new Sequence("axiom");
137:
138: s.add(structure());
139: Alternation a = new Alternation();
140:
141: a.add(ruleDef());
142: a.add(new Empty());
143: s.add(a);
144:
145: s.setAssembler(new AxiomAssembler());
146: return s;
147: }
148:
149: /**
150: * Using the given parser, this method composes a new
151: * parser with the grammar:
152: *
153: * commaList(p) = p (',' p)*;
154: *
155: * The Logikus language uses this construction several
156: * times.
157: */
158: protected static Sequence commaList(Parser p) {
159: Sequence commaP = new Track();
160:
161: commaP.add(new Symbol(',').discard());
162: commaP.add(p);
163:
164: Sequence s = new Sequence();
165:
166: s.add(p);
167: s.add(new Repetition(commaP));
168: return s;
169: }
170:
171: /**
172: * Return a parser that recognizes the grammar:
173: *
174: * <blockquote><pre>
175: * comparison = operator '(' arg ',' arg ')';
176: * </pre></blockquote>
177: *
178: * @return a parser that recognizes a comparison
179: */
180: public Sequence comparison() {
181: Track t = new Track("comparison");
182:
183: t.add(operator());
184: t.add(new Symbol('(').discard());
185: t.add(arg());
186: t.add(new Symbol(',').discard());
187: t.add(arg());
188: t.add(new Symbol(')').discard());
189: t.setAssembler(new ComparisonAssembler());
190: return t;
191: }
192:
193: /**
194: * Return a parser that recognizes the grammar:
195: *
196: * <blockquote><pre>
197: * condition = structure | not | evaluation | comparison |
198: * list;
199: * </pre></blockquote>
200: *
201: * @return a parser that recognizes a condition
202: */
203: public Alternation condition() {
204: Alternation a = new Alternation("condition");
205:
206: a.add(structure());
207: a.add(not());
208: a.add(evaluation());
209: a.add(comparison());
210: a.add(list());
211: return a;
212: }
213:
214: /**
215: * Return a parser that recognizes the grammar:
216: *
217: * divideFactor = '/' factor;
218: */
219: protected Parser divideFactor() {
220: Sequence s = new Sequence("divideFactor");
221:
222: s.add(new Symbol('/').discard());
223: s.add(factor());
224: s.setAssembler(new ArithmeticAssembler('/'));
225: return s;
226: }
227:
228: /**
229: * Return a parser that recognizes the grammar:
230: *
231: * evaluation = '#' '(' arg ',' arg ')';
232: *
233: * For example, this parser will recognize
234: * "#(X, 12321/111)", translating it to an Evaluation
235: * object. When asked to prove itself, the Evaluation
236: * object will unify its first term with the value of
237: * its second term.
238: */
239: protected Parser evaluation() {
240:
241: Track t = new Track("evaluation");
242:
243: t.add(new Symbol('#').discard());
244: t.add(new Symbol('(').discard());
245: t.add(arg());
246: t.add(new Symbol(',').discard());
247: t.add(arg());
248: t.add(new Symbol(')').discard());
249: t.setAssembler(new EvaluationAssembler());
250: return t;
251: }
252:
253: /**
254: * Return a parser that recognizes the grammar:
255: *
256: * expression = phrase ('+' phrase | '-' phrase)*;
257: */
258: protected Parser expression() {
259:
260: /*
261: * This use of a static variable avoids the infinite
262: * recursion inherent in the language definition.
263: */
264: if (expression == null) {
265: expression = new Sequence("expression");
266: expression.add(phrase());
267: Alternation a = new Alternation();
268:
269: a.add(plusPhrase());
270: a.add(minusPhrase());
271: expression.add(new Repetition(a));
272: }
273: return expression;
274: }
275:
276: /**
277: * Return a parser that recognizes the grammar:
278: *
279: * factor = '(' expression ')' | Num | QuotedString | variable;
280: */
281: protected Parser factor() {
282: Alternation a = new Alternation("factor");
283: Sequence s = new Sequence();
284:
285: s.add(new Symbol('(').discard());
286: s.add(expression());
287: s.add(new Symbol(')').discard());
288: a.add(s);
289: a.add(num());
290: a.add(string());
291: a.add(variable());
292: return a;
293: }
294:
295: /**
296: * Return a parser that recognizes the grammar:
297: *
298: * functor = '.' | LowercaseWord | UppercaseWord;
299: */
300: protected Parser functor() {
301: Alternation a = new Alternation("functor");
302:
303: a.add(new LowercaseWord());
304: a.add(new UppercaseWord());
305: a.add(new Symbol('.'));
306: return a;
307: }
308:
309: /**
310: * Return a parser that recognizes the grammar:
311: *
312: * <blockquote><pre>
313: * list = '[' (listContents | Empty) ']';
314: * </pre></blockquote>
315: *
316: * The class comment gives the complete grammar for lists,
317: * as part of the Logikus grammar.
318: *
319: * @return a parser that recognizes a list
320: */
321: public Sequence list() {
322: if (list == null) {
323: list = new Track("list");
324: list.add(new Symbol('[')); // push this, as a fence
325:
326: Alternation a = new Alternation();
327:
328: a.add(listContents());
329: a.add(new Empty().setAssembler(new ListAssembler()));
330:
331: list.add(a);
332: list.add(new Symbol(']').discard());
333: }
334: return list;
335: }
336:
337: /**
338: * Return a parser that recognizes the grammar:
339: *
340: * listContents = commaList(term) listTail;
341: */
342: protected Parser listContents() {
343: Sequence s = commaList(term());
344:
345: s.add(listTail());
346: return s;
347: }
348:
349: /**
350: * Return a parser that recognizes the grammar:
351: *
352: * listTail = ('|' (variable | list)) | Empty;
353: */
354: protected Parser listTail() {
355: Alternation tail = new Alternation();
356:
357: tail.add(variable());
358: tail.add(list());
359:
360: Track barTail = new Track("bar tail");
361:
362: barTail.add(new Symbol('|').discard());
363: barTail.add(tail);
364: barTail.setAssembler(new ListWithTailAssembler());
365:
366: Alternation a = new Alternation();
367:
368: a.add(barTail);
369: a.add(new Empty().setAssembler(new ListAssembler()));
370: return a;
371: }
372:
373: /**
374: * Return a parser that recognizes the grammar:
375: *
376: * minusPhrase = '-' phrase;
377: */
378: protected Parser minusPhrase() {
379: Sequence s = new Sequence("minusPhrase");
380:
381: s.add(new Symbol('-').discard());
382: s.add(phrase());
383: s.setAssembler(new ArithmeticAssembler('-'));
384: return s;
385: }
386:
387: /**
388: * Return a parser that recognizes the grammar:
389: *
390: * not = "not" structure;
391: */
392: protected Parser not() {
393: Track t = new Track("not");
394:
395: t.add(new Literal("not").discard());
396: t.add(structure());
397: t.setAssembler(new NotAssembler());
398: return t;
399: }
400:
401: /**
402: * Return a parser that recognizes a number and stacks a corresponding atom.
403: */
404: public Parser num() {
405: Parser n = new Num();
406:
407: n.setAssembler(new AtomAssembler());
408: return n;
409: }
410:
411: /**
412: * Return a parser that recognizes the grammar:
413: *
414: * operator = '<' | '>' | '=' | "<=" | ">=" | "!=" ;
415: */
416: protected Parser operator() {
417: Alternation a = new Alternation("operator");
418:
419: a.add(new Symbol('<'));
420: a.add(new Symbol('>'));
421: a.add(new Symbol('='));
422: a.add(new Symbol("<="));
423: a.add(new Symbol(">="));
424: a.add(new Symbol("!="));
425: return a;
426: }
427:
428: /**
429: * Return a parser that recognizes the grammar:
430: *
431: * phrase = factor ('*' factor | '/' factor)*;
432: */
433: protected Parser phrase() {
434: Sequence phrase = new Sequence("phrase");
435:
436: phrase.add(factor());
437: Alternation a = new Alternation();
438:
439: a.add(timesFactor());
440: a.add(divideFactor());
441: phrase.add(new Repetition(a));
442: return phrase;
443: }
444:
445: /**
446: * Return a parser that recognizes the grammar:
447: *
448: * plusPhrase = '+' phrase;
449: */
450: protected Parser plusPhrase() {
451: Sequence s = new Sequence("plusPhrase");
452:
453: s.add(new Symbol('+').discard());
454: s.add(phrase());
455: s.setAssembler(new ArithmeticAssembler('+'));
456: return s;
457: }
458:
459: /**
460: * Return a parser that recognizes the grammar:
461: *
462: * <blockquote><pre>
463: * query = commaList(condition);
464: * </pre></blockquote>
465: *
466: * @return a parser that recognizes a query
467: */
468: public static Parser query() {
469: Parser p = commaList(new LogikusParser().condition());
470:
471: p.setAssembler(new AxiomAssembler());
472: return p;
473: }
474:
475: /**
476: * Return a parser that recognizes the grammar:
477: *
478: * ruleDef = ":-" commaList(condition);
479: */
480: protected Parser ruleDef() {
481: Track t = new Track("rule definition");
482:
483: t.add(new Symbol(":-").discard());
484: t.add(commaList(condition()));
485: return t;
486: }
487:
488: /**
489: * Return a parser that recognizes the grammar:
490: *
491: * <blockquote><pre>
492: * axiom = condition (ruleDefinition | empty);
493: * </pre></blockquote>
494: *
495: * @return a parser that recognizes an axiom
496: */
497: public static Parser start() {
498: return new LogikusParser().axiom();
499: }
500:
501: /**
502: * Return a parser that recognizes a number and stacks a corresponding atom.
503: */
504: public Parser string() {
505: Parser str = new QuotedString();
506:
507: str.setAssembler(new AtomAssembler());
508: return str;
509: }
510:
511: /**
512: * Return a parser that recognizes the grammar:
513: *
514: * structure = functor ('(' commaList(term) ')');
515: *
516: * This definition of structure accounts for normal-looking
517: * structures that have a string as a functor. Strictly
518: * speaking, numbers and lists are also structures. The
519: * definition for <code>term</code> includes these.
520: */
521: protected Parser structure() {
522: if (structure == null) {
523: structure = new Sequence("structure");
524:
525: Sequence s = new Sequence("s");
526:
527: structure.add(functor());
528:
529: Track t = new Track("list in parens");
530:
531: t.add(new Symbol('(')); // push this as a fence
532: t.add(commaList(term()));
533: t.add(new Symbol(')').discard());
534:
535: Alternation a = new Alternation();
536:
537: a.add(t.setAssembler(new StructureWithTermsAssembler()));
538:
539: // no longer allowing the empty structure, handling variables differently
540: // a.add(new Empty().setAssembler(new AtomAssembler()));
541:
542: structure.add(a);
543: }
544: return structure;
545: }
546:
547: /**
548: * Return a parser that recognizes the grammar:
549: *
550: * term = structure | Num | QuotedString | list | variable;
551: */
552: protected Parser term() {
553: Alternation a = new Alternation("term");
554:
555: a.add(structure());
556: a.add(num());
557: a.add(string());
558: a.add(list());
559: a.add(variable());
560: return a;
561: }
562:
563: /**
564: * Return a parser that recognizes the grammar:
565: *
566: * timesFactor = '*' factor;
567: */
568: protected Parser timesFactor() {
569: Sequence s = new Sequence("timesFactor");
570:
571: s.add(new Symbol('*').discard());
572: s.add(factor());
573: s.setAssembler(new ArithmeticAssembler('*'));
574: return s;
575: }
576:
577: /**
578: * Return a parser that recognizes the grammar:
579: *
580: * variable = LowercaseWord | UppercaseWord | '_';
581: *
582: * The underscore represents and will translate to an
583: * anonymous variable.
584: */
585: protected Parser variable() {
586: // Parser word = new Word();
587: // word.setAssembler(new VariableAssembler());
588:
589: Parser lowerCase = new LowercaseWord();
590:
591: lowerCase.setAssembler(new VariableAssembler());
592: Parser upperCase = new UppercaseWord();
593:
594: upperCase.setAssembler(new VariableAssembler());
595:
596: Parser anon = new Symbol('_').discard();
597:
598: anon.setAssembler(new AnonymousAssembler());
599:
600: Alternation a = new Alternation();
601:
602: // a.add(word);
603: a.add(lowerCase);
604: a.add(upperCase);
605: a.add(anon);
606: return a;
607: }
608: }
|