Lines Matching +full:turing +full:- +full:complete
21 `Operator-Precedence
22 Parsing <http://en.wikipedia.org/wiki/Operator-precedence_parser>`_ to
37 .. code-block:: ocaml
39 (* expr - Base type for all expression nodes. *)
55 .. code-block:: ocaml
66 This is all (intentionally) rather straight-forward: variables capture
76 Turing-complete; we'll fix that in a later installment. The two things
80 .. code-block:: ocaml
82 (* proto - This type represents the "prototype" for a function, which captures
87 (* func - This type represents a function definition itself. *)
107 .. code-block:: ocaml
119 particular user-friendly, but it will be enough for our tutorial. These
133 the tutorial <OCamlLangImpl6.html#user-defined-unary-operators>`_. In order to parse an
137 .. code-block:: ocaml
145 | [< 'Token.Number n >] -> Ast.Number n
159 .. code-block:: ocaml
162 | [< 'Token.Kwd '('; e=parse_expr; 'Token.Kwd ')' ?? "expected ')'" >] -> e
190 .. code-block:: ocaml
195 | [< 'Token.Ident id; stream >] ->
197 | [< e=parse_expr; stream >] ->
199 | [< 'Token.Kwd ','; e=parse_args (e :: accumulator) >] -> e
200 | [< >] -> e :: accumulator
202 | [< >] -> accumulator
208 'Token.Kwd ')' ?? "expected ')'">] ->
212 | [< >] -> Ast.Variable id
219 it uses *look-ahead* to determine if the current identifier is a stand
228 .. code-block:: ocaml
230 | [< >] -> raise (Stream.Error "unknown token when expecting an expression.")
245 to use `Operator-Precedence
246 Parsing <http://en.wikipedia.org/wiki/Operator-precedence_parser>`_.
250 .. code-block:: ocaml
252 (* binop_precedence - This holds the precedence for each binary operator that is
256 (* precedence - Get the precedence of the pending binary operator token. *)
257 let precedence c = try Hashtbl.find binop_precedence c with Not_found -> -1
266 Hashtbl.add Parser.binop_precedence '-' 20;
273 the current token, or -1 if the token is not a binary operator. Having a
278 fixed-size array).
294 .. code-block:: ocaml
299 | [< lhs=parse_primary; stream >] -> parse_bin_rhs 0 lhs stream
316 .. code-block:: ocaml
323 | Some (Token.Kwd c) when Hashtbl.mem binop_precedence c ->
332 -1, this check implicitly knows that the pair-stream ends when the token
337 .. code-block:: ocaml
348 | Some (Token.Kwd c2) ->
354 Now that we parsed the left-hand side of an expression and one pair of
361 .. code-block:: ocaml
375 .. code-block:: ocaml
399 .. code-block:: ocaml
402 | Some (Token.Kwd c2) ->
408 | _ -> rhs
428 non-trivial lines), we correctly handle fully general binary expression
444 straight-forward and not very interesting (once you've survived
447 .. code-block:: ocaml
453 | [< 'Token.Ident id; e=parse_args (id::accumulator) >] -> e
454 | [< >] -> accumulator
461 'Token.Kwd ')' ?? "expected ')' in prototype" >] ->
465 | [< >] ->
471 .. code-block:: ocaml
475 | [< 'Token.Def; p=parse_prototype; e=parse_expr >] ->
482 .. code-block:: ocaml
486 | [< 'Token.Extern; e=parse_prototype >] -> e
488 Finally, we'll also let the user type in arbitrary top-level expressions
492 .. code-block:: ocaml
496 | [< e=parse_expr >] ->
507 top-level dispatch loop. There isn't much interesting here, so I'll just
508 include the top-level loop. See `below <#full-code-listing>`_ for full code in the
509 "Top-Level Parsing" section.
511 .. code-block:: ocaml
516 | None -> ()
518 (* ignore top-level semicolons. *)
519 | Some (Token.Kwd ';') ->
523 | Some token ->
526 | Token.Def ->
529 | Token.Extern ->
532 | _ ->
533 (* Evaluate a top-level expression into an anonymous function. *)
535 print_endline "parsed a top-level expr";
536 with Stream.Error s ->
544 The most interesting part of this is that we ignore top-level
548 could type "def foo..." in which case 4+5 is the end of a top-level
550 the expression. Having top-level semicolons allows you to type "4+5;",
556 With just under 300 lines of commented code (240 lines of non-comment,
557 non-blank code), we fully defined our minimal language, including a
562 .. code-block:: bash
569 Parsed a top-level expr
586 Here is the complete code listing for this and the previous chapter.
587 Note that it is fully self-contained: you don't need LLVM or any
591 .. code-block:: bash
606 .. code-block:: ocaml
608 (*===----------------------------------------------------------------------===
610 *===----------------------------------------------------------------------===*)
625 .. code-block:: ocaml
627 (*===----------------------------------------------------------------------===
629 *===----------------------------------------------------------------------===*)
633 | [< ' (' ' | '\n' | '\r' | '\t'); stream >] -> lex stream
635 (* identifier: [a-zA-Z][a-zA-Z0-9] *)
636 | [< ' ('A' .. 'Z' | 'a' .. 'z' as c); stream >] ->
641 (* number: [0-9.]+ *)
642 | [< ' ('0' .. '9' as c); stream >] ->
648 | [< ' ('#'); stream >] ->
652 | [< 'c; stream >] ->
656 | [< >] -> [< >]
659 | [< ' ('0' .. '9' | '.' as c); stream >] ->
662 | [< stream=lex >] ->
666 | [< ' ('A' .. 'Z' | 'a' .. 'z' | '0' .. '9' as c); stream >] ->
669 | [< stream=lex >] ->
671 | "def" -> [< 'Token.Def; stream >]
672 | "extern" -> [< 'Token.Extern; stream >]
673 | id -> [< 'Token.Ident id; stream >]
676 | [< ' ('\n'); stream=lex >] -> stream
677 | [< 'c; e=lex_comment >] -> e
678 | [< >] -> [< >]
681 .. code-block:: ocaml
683 (*===----------------------------------------------------------------------===
685 *===----------------------------------------------------------------------===*)
687 (* expr - Base type for all expression nodes. *)
701 (* proto - This type represents the "prototype" for a function, which captures
706 (* func - This type represents a function definition itself. *)
710 .. code-block:: ocaml
712 (*===---------------------------------------------------------------------===
714 *===---------------------------------------------------------------------===*)
716 (* binop_precedence - This holds the precedence for each binary operator that is
720 (* precedence - Get the precedence of the pending binary operator token. *)
721 let precedence c = try Hashtbl.find binop_precedence c with Not_found -> -1
729 | [< 'Token.Number n >] -> Ast.Number n
732 | [< 'Token.Kwd '('; e=parse_expr; 'Token.Kwd ')' ?? "expected ')'" >] -> e
737 | [< 'Token.Ident id; stream >] ->
739 | [< e=parse_expr; stream >] ->
741 | [< 'Token.Kwd ','; e=parse_args (e :: accumulator) >] -> e
742 | [< >] -> e :: accumulator
744 | [< >] -> accumulator
750 'Token.Kwd ')' ?? "expected ')'">] ->
754 | [< >] -> Ast.Variable id
758 | [< >] -> raise (Stream.Error "unknown token when expecting an expression.")
765 | Some (Token.Kwd c) when Hashtbl.mem binop_precedence c ->
780 | Some (Token.Kwd c2) ->
787 | _ -> rhs
794 | _ -> lhs
799 | [< lhs=parse_primary; stream >] -> parse_bin_rhs 0 lhs stream
805 | [< 'Token.Ident id; e=parse_args (id::accumulator) >] -> e
806 | [< >] -> accumulator
813 'Token.Kwd ')' ?? "expected ')' in prototype" >] ->
817 | [< >] ->
822 | [< 'Token.Def; p=parse_prototype; e=parse_expr >] ->
827 | [< e=parse_expr >] ->
833 | [< 'Token.Extern; e=parse_prototype >] -> e
836 .. code-block:: ocaml
838 (*===----------------------------------------------------------------------===
839 * Top-Level parsing and JIT Driver
840 *===----------------------------------------------------------------------===*)
845 | None -> ()
847 (* ignore top-level semicolons. *)
848 | Some (Token.Kwd ';') ->
852 | Some token ->
855 | Token.Def ->
858 | Token.Extern ->
861 | _ ->
862 (* Evaluate a top-level expression into an anonymous function. *)
864 print_endline "parsed a top-level expr";
865 with Stream.Error s ->
874 .. code-block:: ocaml
876 (*===----------------------------------------------------------------------===
878 *===----------------------------------------------------------------------===*)
885 Hashtbl.add Parser.binop_precedence '-' 20;