Ignore:
Timestamp:
Oct 18, 2008, 12:21:06 AM (12 years ago)
Author:
orlov
Message:
  • Earley algorithm in Refal-5 without ofpen variables.
File:
1 edited

Legend:

Unmodified
Added
Removed
  • applications/trunk/LFC/Earley/Earley.ref

    r3977 r3978  
     1* $Id$
     2*
    13* Practical Earley Parsing
    24* Aycock and Horspool
     
    79Check {
    810  (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     };
     11    <Parse (e.grammar) (e.string) () (((TYPE START) (DOT (TYPE t.name)) ())) () ()> : e.sets (e.last) =
     12    <FindSuccessRule t.name e.last>;
     13}
     14
     15FindSuccessRule {
     16  t.name ((TYPE t.name e.info) e.prod (DOT) ()) e.rules = (e.info) (e.prod);
     17  t.name t.rule e.rules = <FindSuccessRule t.name e.rules>;
     18  t.name = "Parsing failed";
    1419}
    1520
    1621Earley {
    17   (e.grammar) t.type e.string = <Parse (e.grammar) (e.string) () (((TYPE START) DOT t.type ())) () ()>;
     22  (e.grammar) t.type e.string = <Parse (e.grammar) (e.string) () (((TYPE START) (DOT t.type) ())) () ()>;
    1823}
    1924
    2025* In: (e.grammar) (e.string) e.sets (e.rules) (e.current) (e.next)
    2126Parse {
    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 = ;
    2327  (e.grammar) () (e.step) e.sets () (e.current) () = e.sets (e.current);
    2428  (e.grammar) (s.char e.string) (e.step) e.sets () (e.current) (e.next) =
     
    2630  (e.grammar) (e.string) (e.step) e.sets (t.rule e.rules) (e.current) (e.next), t.rule : {
    2731* Scanner
    28     ((TYPE t.name e.info) e.1 DOT s.char e.2 (e.n)), e.string : {
     32    ((TYPE t.name e.info) e.1 (DOT s.char e.2) (e.n)), e.string : {
    2933      s.char e.rest_chars =
    3034        <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)))>;
     35          (e.next ((TYPE t.name e.info s.char) e.1 s.char (DOT e.2) (e.n)))>;
    3236      e.string =
    3337        <Parse (e.grammar) (e.string) (e.step) e.sets (e.rules) (e.current t.rule) (e.next)>;
    3438    };
    3539* Predictor
    36     (t.type e.1 DOT (TYPE t.name) e.2 (e.n)),
     40    (t.type e.1 (DOT (TYPE t.name) e.2) (e.n)),
    3741      e.current t.rule : e.current2 =
    3842      <Parse (e.grammar) (e.string) (e.step) e.sets
    3943        (<AddPredictions (e.grammar) (e.rules) (e.current2) t.name (e.step)>) (e.current2) (e.next)>;
    4044* Completer
    41     ((TYPE t.name e.info) e.1 DOT (e.n)),
     45    ((TYPE t.name e.info) e.1 (DOT) (e.n)),
    4246      e.current t.rule : e.current2 =
    4347      <Parse (e.grammar) (e.string) (e.step) e.sets
     
    5559AddPredictions2 {
    5660  ((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)>;
     61    ((TYPE t.name) (DOT e.prod) (e.step)) : t.prediction,
     62    <IsIn e.rules t.prediction> : {
     63      True = <AddPredictions2 (e.rest_prods) (e.rules) (e.current) t.name (e.step)>;
     64      False, <IsIn e.current t.prediction> : {
     65        True = <AddPredictions2 (e.rest_prods) (e.rules) (e.current) t.name (e.step)>;
     66        False = <AddPredictions2 (e.rest_prods) (e.rules t.prediction) (e.current) t.name (e.step)>;
    6367      };
    6468    };
     
    7377
    7478AddCompletions2 {
    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>;
     79  (((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,
     80    ((TYPE t.name2 e.info2 (e.info)) e.1 (TYPE t.name) (DOT e.2) (e.step)) : t.completion,
     81    <IsIn e.rules t.completion> : {
     82      True = <AddCompletions2 (e.set) (e.rules) (e.current) t.name e.info>;
     83      False, <IsIn e.current t.completion> : {
     84        True = <AddCompletions2 (e.set) (e.rules) (e.current) t.name e.info>;
     85        False = <AddCompletions2 (e.set) (e.rules t.completion) (e.current) t.name e.info>;
    8286      };
    8387    };
     
    8690}
    8791
     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
    8898$ENTRY Go {
    8999  = <Prout
    90100* 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'>>;
     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'>>;
    93103}
    94104
Note: See TracChangeset for help on using the changeset viewer.