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

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