Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commita69bc98

Browse files
committed
Implemented a parser for combinators
1 parent9eebf67 commita69bc98

File tree

7 files changed

+90
-21
lines changed

7 files changed

+90
-21
lines changed

‎automata.ml‎

Lines changed: 24 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -1,17 +1,31 @@
1-
letrun_stepxsym=
2-
Fsa.stepSymbol.test x sym|>
1+
letcompiles=
2+
letcompile_automatonfn=
3+
let ch= open_in fnin
4+
let a, assignments=Lexing.from_channel ch|>Compiler.compilein
5+
close_in ch;
6+
Printf.printf"compiled %s:\n" fn;
7+
List.iter (fun (n,i) ->Printf.printf"%s -> %d\n" n i) assignments;
8+
ain
9+
letrecconvert=function
10+
|Combinators.Simplefn ->Combinators.Simple (compile_automaton fn)
11+
|Combinators.Sequencel ->Combinators.Sequence (List.map convert l)
12+
|Combinators.Unionl ->Combinators.Union (List.map convert l)in
13+
Lexing.from_string s|>
14+
Combinator_parser.topCombinator_lexer.top|>
15+
convert
16+
17+
letrun_steptsym=
18+
Combinators.stepSymbol.test t sym|>
319
List.iterAction.run;
4-
x
20+
t
521

622
let()=
7-
ifArray.lengthSys.argv<>2||Sys.argv.(1)="--help"then (
8-
Printf.fprintf stderr"usage: %sinput_string\n"Sys.argv.(0);
23+
ifArray.lengthSys.argv<>3then (
24+
Printf.fprintf stderr"usage: %sautomata input\n"Sys.argv.(0);
925
exit1
1026
);
11-
let lexbuf=Lexing.from_channel stdinin
12-
let a, assignments=Compiler.compile lexbufin
13-
List.iter (fun (n,i) ->Printf.printf"%s -> %d\n" n i) assignments;
27+
let t= compileSys.argv.(1)in
1428
let steps=
15-
let s=Sys.argv.(1)in
29+
let s=Sys.argv.(2)in
1630
Array.init (String.length s) (funi -> s.[i])in
17-
Array.fold_left run_stepa steps|> ignore
31+
Array.fold_left run_stept steps|> ignore

‎combinator_lexer.mll‎

Lines changed: 8 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,8 @@
1+
rule top= parse
2+
| [' ''\t'] { top lexbuf }
3+
|";"|"->"|"<" {Combinator_parser.BEFORE }
4+
|"(" {Combinator_parser.LPAR }
5+
|")" {Combinator_parser.RPAR }
6+
|"||" {Combinator_parser.AND }
7+
| ['0'-'9''A'-'Z''a'-'z''.''_']+as fn {Combinator_parser.FILENAME fn }
8+
| eof {Combinator_parser.EOF }

‎combinator_parser.mly‎

Lines changed: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,31 @@
1+
%tokenLPAR
2+
%tokenRPAR
3+
%tokenBEFORE
4+
%tokenAND
5+
%token<string>FILENAME
6+
%tokenEOF
7+
8+
%start<stringCombinators.t> top
9+
%{
10+
(* one level is enough (easy proof)*)
11+
letsimplifyt=match twith
12+
|Combinators.Sequence [x] -> x
13+
|Combinators.Union [x] -> x
14+
|_ -> t
15+
%}
16+
%%
17+
18+
t:
19+
| fn=FILENAME {Combinators.Simple fn }
20+
|LPAR ; e= union ;RPAR { simplify (Combinators.Union e) }
21+
22+
seq:
23+
| t= t { [t] }
24+
| t= t ;BEFORE ; l= seq {t ::l }
25+
26+
union:
27+
| s= seq { [simplify (Combinators.Sequence s)] }
28+
| s= seq ;AND ; t= union { simplify (Combinators.Sequence s) :: t }
29+
30+
top:
31+
| l= union ;EOF { simplify (Combinators.Union l) }

‎combinators.ml‎

Lines changed: 14 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -1,15 +1,23 @@
1-
type('sym, 'a) t=
2-
|Simpleof ('sym,'a)Fsa.t
3-
|Firstof ('sym,'a)tlist
4-
|Bothof ('sym,'a)tlist
1+
type'a t=
2+
|Simpleof'a
3+
|Sequenceof'atlist
4+
|Unionof'atlist
5+
6+
letdumpt=
7+
letrecf=function
8+
|Simples -> s
9+
|Sequencel ->"("^String.concat";" (List.map f l)^")"
10+
|Unionl ->"("^String.concat" ||" (List.map f l)^")"in
11+
Printf.printf"%s\n" (f t);
12+
t
513

614
letrecsteptestxt=match xwith
715
|Simplex ->
816
Fsa.step test x t
9-
|Bothl ->
17+
|Unionl ->
1018
List.map (funx -> step test x t) l|>
1119
List.concat
12-
|Firstl ->
20+
|Sequencel ->
1321
List.fold_left (funaccx ->
1422
if acc=[]then
1523
step test x t

‎combinators.mli‎

Lines changed: 8 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -1,7 +1,10 @@
1-
type('sym, 'a) t=
2-
|Simpleof('sym,'a)Fsa.t
3-
|Firstof('sym,'a)tlist(* yields the 1st action list if it's not []*)
4-
|Bothof('sym,'a)tlist(* keep both action lists (left then right)*)
1+
type'a t=
2+
|Simpleof'a
3+
|Sequenceof'atlist(* yields the 1st action list if it's not []*)
4+
|Unionof'atlist(* keep both action lists (left then right)*)
55

6-
valstep: ('sym ->'syms ->bool) -> ('syms,'a)t ->'sym ->'alist
6+
valdump:stringt ->stringt
7+
(* dump t dumps the input and returns it unchanged*)
8+
9+
valstep: ('sym ->'syms ->bool) -> ('syms,'a)Fsa.tt ->'sym ->'alist
710
(* step test x t processes an input t and returns the corresponding actions*)

‎fsa.ml‎

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -67,3 +67,5 @@ let closure x i =
6767

6868
(* TODO remove useless states? use a map for the states we rename*)
6969
(* TODO save as a list of tuples with the biggest index first to avoid O(n^2)*)
70+
71+
letclone{states; state}= {states; state}

‎fsa.mli‎

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -14,3 +14,6 @@ val step: ('sym -> 'syms -> bool) -> ('syms, 'a) t -> 'sym -> 'a list
1414

1515
valclosure:_t ->state -> [>`Invalidofstate |`Visitedofstatelist ]
1616
(* closure x i computes the transitive closure of x starting from state i.*)
17+
18+
valclone: ('sym,'a)t -> ('sym,'a)t
19+
(* clone x clones the given automaton (and its current state)*)

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp