source: applications/trunk/LFC/Earley/Earley.ref @ 3980

Last change on this file since 3980 was 3980, checked in by orlov, 12 years ago
  • Earley algorithm in Refal-5 without repeated et-variables.
  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 4.8 KB
Line 
1* $Id: Earley.ref 3980 2008-10-18 20:45:34Z orlov $
2*
3* Practical Earley Parsing
4* Aycock and Horspool
5
6* This version takes any context free grammars but with nullable non-terminals
7* (rules of a kind [E -> ] are not allowed).
8
9Check {
10  (e.grammar) (TYPE s.name) e.string,
11    <Parse (e.grammar) (e.string) () (((TYPE START) (DOT (TYPE s.name)) ())) () ()> : e.sets (e.last) =
12    <FindSuccessRule s.name e.last>;
13}
14
15FindSuccessRule {
16  s.name ((TYPE s.name e.info) e.prod (DOT) ()) e.rules = (e.info) (e.prod);
17  s.name t.rule e.rules = <FindSuccessRule s.name e.rules>;
18  s.name = "Parsing failed";
19}
20
21Earley {
22  (e.grammar) t.type e.string = <Parse (e.grammar) (e.string) () (((TYPE START) (DOT t.type) ())) () ()>;
23}
24
25* In: (e.grammar) (e.string) e.sets (e.rules) (e.current) (e.next)
26Parse {
27  (e.grammar) () (e.step) e.sets () (e.current) () = e.sets (e.current);
28  (e.grammar) (s.char e.string) (e.step) e.sets () (e.current) (e.next) =
29    <Parse (e.grammar) (e.string) (e.step I) e.sets (e.current) (e.next) () ()>;
30  (e.grammar) (e.string) (e.step) e.sets (t.rule e.rules) (e.current) (e.next), t.rule : {
31* Scanner
32    ((TYPE s.name e.info) e.1 (DOT s.char e.2) (e.n)), e.string : {
33      s.char e.rest_chars =
34        <Parse (e.grammar) (e.string) (e.step) e.sets (e.rules) (e.current t.rule)
35          (e.next ((TYPE s.name e.info s.char) e.1 s.char (DOT e.2) (e.n)))>;
36      e.string =
37        <Parse (e.grammar) (e.string) (e.step) e.sets (e.rules) (e.current t.rule) (e.next)>;
38    };
39* Predictor
40    (t.type e.1 (DOT (TYPE s.name) e.2) (e.n)),
41      e.current t.rule : e.current2 =
42      <Parse (e.grammar) (e.string) (e.step) e.sets
43        (<AddPredictions (e.grammar) (e.rules) (e.current2) s.name (e.step)>) (e.current2) (e.next)>;
44* Completer
45    ((TYPE s.name e.info) e.1 (DOT) (e.n)),
46      e.current t.rule : e.current2 =
47      <Parse (e.grammar) (e.string) (e.step) e.sets
48        (<AddCompletions (e.n) (e.sets) (e.rules) (e.current2) s.name e.info>) (e.current2) (e.next)>;
49  };
50}
51
52AddPredictions {
53  ((PROD (TYPE s.name) e.prods) e.grammar) (e.rules) (e.current) s.name (e.step) =
54    <AddPredictions (e.grammar) (<AddPredictions2 (e.prods) (e.rules) (e.current) s.name (e.step)>) (e.current) s.name (e.step)>;
55  (t.prod e.grammar) (e.rules) (e.current) s.name (e.step) = <AddPredictions (e.grammar) (e.rules) (e.current) s.name (e.step)>;
56  () (e.rules) (e.current) s.name (e.step) = e.rules;
57}
58
59AddPredictions2 {
60  ((e.prod) e.rest_prods) (e.rules) (e.current) s.name (e.step),
61    ((TYPE s.name) (DOT e.prod) (e.step)) : t.prediction,
62    <IsIn e.rules t.prediction> : {
63      True = <AddPredictions2 (e.rest_prods) (e.rules) (e.current) s.name (e.step)>;
64      False, <IsIn e.current t.prediction> : {
65        True = <AddPredictions2 (e.rest_prods) (e.rules) (e.current) s.name (e.step)>;
66        False = <AddPredictions2 (e.rest_prods) (e.rules t.prediction) (e.current) s.name (e.step)>;
67      };
68    };
69  () (e.rules) (e.current) s.name (e.step) = e.rules;
70}
71
72AddCompletions {
73  (I e.n) (t.set e.rest_sets) (e.rules) (e.current) s.name e.info = <AddCompletions (e.n) (e.rest_sets) (e.rules) (e.current) s.name e.info>;
74  () ((e.set) e.rest_sets) (e.rules) (e.current) s.name e.info = <AddCompletions2 (e.set) (e.rules) (e.current) s.name e.info>;
75  () () (e.rules) (e.current) s.name e.info = e.rules;
76}
77
78AddCompletions2 {
79  (((TYPE s.name2 e.info2) e.1 (DOT (TYPE s.name) e.2) (e.step)) e.set) (e.rules) (e.current) s.name e.info,
80    ((TYPE s.name2 e.info2 (e.info)) e.1 (TYPE s.name) (DOT e.2) (e.step)) : t.completion,
81    <IsIn e.rules t.completion> : {
82      True = <AddCompletions2 (e.set) (e.rules) (e.current) s.name e.info>;
83      False, <IsIn e.current t.completion> : {
84        True = <AddCompletions2 (e.set) (e.rules) (e.current) s.name e.info>;
85        False = <AddCompletions2 (e.set) (e.rules t.completion) (e.current) s.name e.info>;
86      };
87    };
88  (t.rule e.set) (e.rules) (e.current) s.name e.info = <AddCompletions2 (e.set) (e.rules) (e.current) s.name e.info>;
89  () (e.rules) (e.current) s.name e.info = e.rules;
90}
91
92IsIn {
93  t.1 e.set t.1 = True;
94  t.1 e.set t.2 = <IsIn e.set t.2>;
95  t.2 = False;
96}
97
98$ENTRY Go {
99  = <Prout
100* E -> E '+' E | 'n'
101      <Check ((PROD (TYPE "E") ((TYPE "E") '+' (TYPE "E")) ('n'))) (TYPE "E") 'n+n'> '\n'
102      <Check ((PROD (TYPE "E") ((TYPE "E") '+' (TYPE "E"))) (PROD (TYPE "E") ('n'))) (TYPE "E") 'n+n+n'>>;
103}
104
105* Main =
106*   <Init (PROD (TYPE ('E')) ((TYPE ('E')) '+' (TYPE ('E'))) ('n'))>,
107*   <Check (TYPE ('E')) ('n+n')>,
108*   <PrintLn>,
109*   <Check (TYPE ('E')) ('n+n+n')>,
110*   <PrintLn>,
111*   <Init (PROD (TYPE ('S')) ((TYPE ('A')) (TYPE ('A')) (TYPE ('A')) (TYPE ('A'))))
112*         (PROD (TYPE ('A')) ('a') ((TYPE ('E'))))
113*         (PROD (TYPE ('E')) ())>,
114*   <Check (TYPE ('S')) ('a')>,
115*   <PrintLn>,
116*   <Init (PROD (TYPE ('T')) ((TYPE ('A'))) ((TYPE ('B'))))
117*         (PROD (TYPE ('A')) ('x'))
118*         (PROD (TYPE ('B')) ('x'))>,
119*   <Check (TYPE ('T')) ('x')>;
Note: See TracBrowser for help on using the repository browser.