Changeset 3978 for applications/trunk/LFC/Earley/Earley.ref

Timestamp:

Oct 18, 2008, 12:21:06 AM (12 years ago)

Author:

orlov

Message:

• Earley algorithm in Refal-5 without ofpen variables.

File:

• applications/trunk/LFC/Earley/Earley.ref (modified) (6 diffs)

applications/trunk/LFC/Earley/Earley.ref

@@ +1 @@
+* $Id$
+*
 * Practical Earley Parsing
 * Aycock and Horspool
@@ -7 +9 @@
 Check {
   (e.grammar) (TYPE t.name) e.string,
-    <Parse (e.grammar) (e.string) () (((TYPE START) DOT (TYPE t.name) ())) () ()> : e.sets (e.last),
-    e.last : {
-      e.l ((TYPE t.name e.info) e.prod DOT ()) e.r = (e.info) (e.prod);
-      e.last = "Can not parse '"e.string"' as "(TYPE t.name);
-    };
+    <Parse (e.grammar) (e.string) () (((TYPE START) (DOT (TYPE t.name)) ())) () ()> : e.sets (e.last) =
+    <FindSuccessRule t.name e.last>;
+}
+
+FindSuccessRule {
+  t.name ((TYPE t.name e.info) e.prod (DOT) ()) e.rules = (e.info) (e.prod);
+  t.name t.rule e.rules = <FindSuccessRule t.name e.rules>;
+  t.name = "Parsing failed";
 }
 
 Earley {
-  (e.grammar) t.type e.string = <Parse (e.grammar) (e.string) () (((TYPE START) DOT t.type ())) () ()>;
+  (e.grammar) t.type e.string = <Parse (e.grammar) (e.string) () (((TYPE START) (DOT t.type) ())) () ()>;
 }
 
 * In: (e.grammar) (e.string) e.sets (e.rules) (e.current) (e.next)
 Parse {
-  (e.grammar) (e.string) e.sets (e.rules) (e.current) (e.next), <Print (e.grammar) (e.string) e.sets (e.rules) (e.current) (e.next)> : s.x = ;
   (e.grammar) () (e.step) e.sets () (e.current) () = e.sets (e.current);
   (e.grammar) (s.char e.string) (e.step) e.sets () (e.current) (e.next) =
@@ -26 +30 @@
   (e.grammar) (e.string) (e.step) e.sets (t.rule e.rules) (e.current) (e.next), t.rule : {
 * Scanner
-    ((TYPE t.name e.info) e.1 DOT s.char e.2 (e.n)), e.string : {
+    ((TYPE t.name e.info) e.1 (DOT s.char e.2) (e.n)), e.string : {
       s.char e.rest_chars =
         <Parse (e.grammar) (e.string) (e.step) e.sets (e.rules) (e.current t.rule)
-          (e.next ((TYPE t.name e.info s.char) e.1 s.char DOT e.2 (e.n)))>;
+          (e.next ((TYPE t.name e.info s.char) e.1 s.char (DOT e.2) (e.n)))>;
       e.string =
         <Parse (e.grammar) (e.string) (e.step) e.sets (e.rules) (e.current t.rule) (e.next)>;
     };
 * Predictor
-    (t.type e.1 DOT (TYPE t.name) e.2 (e.n)),
+    (t.type e.1 (DOT (TYPE t.name) e.2) (e.n)),
       e.current t.rule : e.current2 =
       <Parse (e.grammar) (e.string) (e.step) e.sets
         (<AddPredictions (e.grammar) (e.rules) (e.current2) t.name (e.step)>) (e.current2) (e.next)>;
 * Completer
-    ((TYPE t.name e.info) e.1 DOT (e.n)),
+    ((TYPE t.name e.info) e.1 (DOT) (e.n)),
       e.current t.rule : e.current2 =
       <Parse (e.grammar) (e.string) (e.step) e.sets
@@ -55 +59 @@
 AddPredictions2 {
   ((e.prod) e.rest_prods) (e.rules) (e.current) t.name (e.step),
-    ((TYPE t.name) DOT e.prod (e.step)) : t.prediction,
-    e.rules : {
-      e.l t.prediction e.r = <AddPredictions2 (e.rest_prods) (e.rules) (e.current) t.name (e.step)>;
-      e.rules, e.current : {
-        e.l t.prediction e.r = <AddPredictions2 (e.rest_prods) (e.rules) (e.current) t.name (e.step)>;
-        e.current = <AddPredictions2 (e.rest_prods) (e.rules t.prediction) (e.current) t.name (e.step)>;
+    ((TYPE t.name) (DOT e.prod) (e.step)) : t.prediction,
+    <IsIn e.rules t.prediction> : {
+      True = <AddPredictions2 (e.rest_prods) (e.rules) (e.current) t.name (e.step)>;
+      False, <IsIn e.current t.prediction> : {
+        True = <AddPredictions2 (e.rest_prods) (e.rules) (e.current) t.name (e.step)>;
+        False = <AddPredictions2 (e.rest_prods) (e.rules t.prediction) (e.current) t.name (e.step)>;
       };
     };
@@ -73 +77 @@
 
 AddCompletions2 {
-  (((TYPE t.name2 e.info2) e.1 DOT (TYPE t.name) e.2 (e.step)) e.set) (e.rules) (e.current) t.name e.info,
-    ((TYPE t.name2 e.info2 (e.info)) e.1 (TYPE t.name) DOT e.2 (e.step)) : t.completion,
-    e.rules : {
-      e.l t.completion e.r = <AddCompletions2 (e.set) (e.rules) (e.current) t.name e.info>;
-      e.rules, e.current : {
-        e.l t.completion e.r = <AddCompletions2 (e.set) (e.rules) (e.current) t.name e.info>;
-        e.current = <AddCompletions2 (e.set) (e.rules t.completion) (e.current) t.name e.info>;
+  (((TYPE t.name2 e.info2) e.1 (DOT (TYPE t.name) e.2) (e.step)) e.set) (e.rules) (e.current) t.name e.info,
+    ((TYPE t.name2 e.info2 (e.info)) e.1 (TYPE t.name) (DOT e.2) (e.step)) : t.completion,
+    <IsIn e.rules t.completion> : {
+      True = <AddCompletions2 (e.set) (e.rules) (e.current) t.name e.info>;
+      False, <IsIn e.current t.completion> : {
+        True = <AddCompletions2 (e.set) (e.rules) (e.current) t.name e.info>;
+        False = <AddCompletions2 (e.set) (e.rules t.completion) (e.current) t.name e.info>;
       };
     };
@@ -86 +90 @@
 }
 
+IsIn {
+  t.1 e.set t.1 = True;
+  t.1 e.set t.2 = <IsIn e.set t.2>;
+  t.2 = False;
+}
+
 $ENTRY Go {
   = <Prout
 * E -> E '+' E | 'n'
-      <Check ((PROD (TYPE ('E')) ((TYPE ('E')) '+' (TYPE ('E'))) ('n'))) (TYPE ('E')) 'mn'> '\n' >;
-*      <Check ((PROD (TYPE ('E')) ((TYPE ('E')) '+' (TYPE ('E')))) (PROD (TYPE ('E')) ('n'))) (TYPE ('E')) 'n+n+n'>>;
+      <Check ((PROD (TYPE ('E')) ((TYPE ('E')) '+' (TYPE ('E'))) ('n'))) (TYPE ('E')) 'n+n'> '\n'
+      <Check ((PROD (TYPE ('E')) ((TYPE ('E')) '+' (TYPE ('E')))) (PROD (TYPE ('E')) ('n'))) (TYPE ('E')) 'n+n+n'>>;
 }