123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170 |
- <html>
- <head>
- <meta http-equiv="Content-Type" content="text/html; charset=US-ASCII">
- <title>Syntax Diagram</title>
- <link rel="stylesheet" href="../../../../../../../doc/src/boostbook.css" type="text/css">
- <meta name="generator" content="DocBook XSL Stylesheets V1.79.1">
- <link rel="home" href="../../index.html" title="Spirit X3 3.0.4">
- <link rel="up" href="../abstracts.html" title="Abstracts">
- <link rel="prev" href="../abstracts.html" title="Abstracts">
- <link rel="next" href="parsing_expression_grammar.html" title="Parsing Expression Grammar">
- </head>
- <body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF">
- <table cellpadding="2" width="100%"><tr>
- <td valign="top"><img alt="Boost C++ Libraries" width="277" height="86" src="../../../../../../../boost.png"></td>
- <td align="center"><a href="../../../../../../../index.html">Home</a></td>
- <td align="center"><a href="../../../../../../../libs/libraries.htm">Libraries</a></td>
- <td align="center"><a href="http://www.boost.org/users/people.html">People</a></td>
- <td align="center"><a href="http://www.boost.org/users/faq.html">FAQ</a></td>
- <td align="center"><a href="../../../../../../../more/index.htm">More</a></td>
- </tr></table>
- <hr>
- <div class="spirit-nav">
- <a accesskey="p" href="../abstracts.html"><img src="../../../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../abstracts.html"><img src="../../../../../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../../index.html"><img src="../../../../../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="parsing_expression_grammar.html"><img src="../../../../../../../doc/src/images/next.png" alt="Next"></a>
- </div>
- <div class="section">
- <div class="titlepage"><div><div><h3 class="title">
- <a name="spirit_x3.abstracts.syntax_diagram"></a><a class="link" href="syntax_diagram.html" title="Syntax Diagram">Syntax Diagram</a>
- </h3></div></div></div>
- <p>
- In the next section, we will deal with Parsing Expression Grammars (PEG)
- <a href="#ftn.spirit_x3.abstracts.syntax_diagram.f0" class="footnote" name="spirit_x3.abstracts.syntax_diagram.f0"><sup class="footnote">[2]</sup></a>, a variant of Extended Backus-Naur Form (EBNF) <a href="#ftn.spirit_x3.abstracts.syntax_diagram.f1" class="footnote" name="spirit_x3.abstracts.syntax_diagram.f1"><sup class="footnote">[3]</sup></a> with a different interpretation. It is easier to understand PEG
- using Syntax Diagrams. Syntax diagrams represent a grammar graphically. It
- was used extensively by Niklaus Wirth <a href="#ftn.spirit_x3.abstracts.syntax_diagram.f2" class="footnote" name="spirit_x3.abstracts.syntax_diagram.f2"><sup class="footnote">[4]</sup></a> in the "Pascal User Manual". Syntax Diagrams are easily
- understandable by programmers due to their similarity to flow charts. The
- isomorphism of the diagrams and functions make them ideal for representing
- <a href="https://en.wikipedia.org/wiki/Recursive_descent_parser" target="_top">Recursive
- Descent</a> parsers which are essentially mutually recursive functions.
- </p>
- <h5>
- <a name="spirit_x3.abstracts.syntax_diagram.h0"></a>
- <span class="phrase"><a name="spirit_x3.abstracts.syntax_diagram.elements"></a></span><a class="link" href="syntax_diagram.html#spirit_x3.abstracts.syntax_diagram.elements">Elements</a>
- </h5>
- <p>
- All diagrams have one entry and one exit point. Arrows connect all possible
- paths through the grammar from the entry point to the exit point.
- </p>
- <div class="blockquote"><blockquote class="blockquote"><p>
- <span class="inlinemediaobject"><img src="../.././images/start_stop.png" alt="start_stop"></span>
- </p></blockquote></div>
- <p>
- Terminals are represented by round boxes. Terminals are atomic and usually
- represent plain characters, strings or tokens.
- </p>
- <div class="blockquote"><blockquote class="blockquote"><p>
- <span class="inlinemediaobject"><img src="../.././images/terminal.png" alt="terminal"></span>
- </p></blockquote></div>
- <p>
- Non-terminals are represented by boxes. Diagrams are modularized using named
- non-terminals. A complex diagram can be broken down into a set of non-terminals.
- Non-terminals also allow recursion (i.e. a non-terminal can call itself).
- </p>
- <div class="blockquote"><blockquote class="blockquote"><p>
- <span class="inlinemediaobject"><img src="../.././images/non-terminal.png" alt="non-terminal"></span>
- </p></blockquote></div>
- <h5>
- <a name="spirit_x3.abstracts.syntax_diagram.h1"></a>
- <span class="phrase"><a name="spirit_x3.abstracts.syntax_diagram.constructs"></a></span><a class="link" href="syntax_diagram.html#spirit_x3.abstracts.syntax_diagram.constructs">Constructs</a>
- </h5>
- <p>
- The most basic composition is the Sequence. B follows A:
- </p>
- <div class="blockquote"><blockquote class="blockquote"><p>
- <span class="inlinemediaobject"><img src="../.././images/sequence.png" alt="sequence"></span>
- </p></blockquote></div>
- <p>
- The ordered choice henceforth we will call <span class="emphasis"><em>alternatives</em></span>.
- In PEG, ordered choice and alternatives are not quite the same. PEG allows
- ambiguity of choice where one or more branches can succeed. In PEG, in case
- of ambiguity, the first one always wins.
- </p>
- <div class="blockquote"><blockquote class="blockquote"><p>
- <span class="inlinemediaobject"><img src="../.././images/alternative.png" alt="alternative"></span>
- </p></blockquote></div>
- <p>
- The optional (zero-or-one):
- </p>
- <div class="blockquote"><blockquote class="blockquote"><p>
- <span class="inlinemediaobject"><img src="../.././images/optional.png" alt="optional"></span>
- </p></blockquote></div>
- <p>
- Now, the loops. We have the zero-or-more and one-or-more:
- </p>
- <div class="blockquote"><blockquote class="blockquote"><p>
- <span class="inlinemediaobject"><img src="../.././images/kleene.png" alt="kleene"></span>
- </p></blockquote></div>
- <div class="blockquote"><blockquote class="blockquote"><p>
- <span class="inlinemediaobject"><img src="../.././images/plus.png" alt="plus"></span>
- </p></blockquote></div>
- <p>
- Take note that, as in PEG, these loops behave greedily. If there is another
- 'A' just before the end-point, it will always fail because the preceding
- loop has already exhausted all 'A's and there is nothing more left. This
- is a crucial difference between PEG and general Context Free Grammars (CFGs).
- This behavior is quite obvious with syntax diagrams as they resemble flow-charts.
- </p>
- <h5>
- <a name="spirit_x3.abstracts.syntax_diagram.h2"></a>
- <span class="phrase"><a name="spirit_x3.abstracts.syntax_diagram.predicates"></a></span><a class="link" href="syntax_diagram.html#spirit_x3.abstracts.syntax_diagram.predicates">Predicates</a>
- </h5>
- <p>
- Now, the following are Syntax Diagram versions of PEG predicates. These are
- not traditionally found in Syntax Diagrams. These are special extensions
- we invented to closely follow PEGs.
- </p>
- <p>
- First, we introduce a new element, the Predicate:
- </p>
- <div class="blockquote"><blockquote class="blockquote"><p>
- <span class="inlinemediaobject"><img src="../.././images/predicate.png" alt="predicate"></span>
- </p></blockquote></div>
- <p>
- This is similar to the conditionals in flow charts where the 'No' branch
- is absent and always signals a failed parse.
- </p>
- <p>
- We have two versions of the predicate, the <span class="emphasis"><em>And-Predicate</em></span>
- and the <span class="emphasis"><em>Not-Predicate</em></span>:
- </p>
- <div class="blockquote"><blockquote class="blockquote"><p>
- <span class="inlinemediaobject"><img src="../.././images/and_predicate.png" alt="and_predicate"></span>
- </p></blockquote></div>
- <div class="blockquote"><blockquote class="blockquote"><p>
- <span class="inlinemediaobject"><img src="../.././images/not_predicate.png" alt="not_predicate"></span>
- </p></blockquote></div>
- <p>
- The <span class="emphasis"><em>And-Predicate</em></span> tries the predicate, P, and succeeds
- if P succeeds, or otherwise fail. The opposite is true with the <span class="emphasis"><em>Not-Predicate</em></span>.
- It tries the predicate, P, and fails if P succeeds, or otherwise succeeds.
- Both versions do a look-ahead but do not consume any input regardless if
- P succeeds or not.
- </p>
- <div class="footnotes">
- <br><hr style="width:100; text-align:left;margin-left: 0">
- <div id="ftn.spirit_x3.abstracts.syntax_diagram.f0" class="footnote"><p><a href="#spirit_x3.abstracts.syntax_diagram.f0" class="para"><sup class="para">[2] </sup></a>
- Bryan Ford: Parsing Expression Grammars: A Recognition-Based Syntactic
- Foundation, <a href="http://pdos.csail.mit.edu/~baford/packrat/popl04/" target="_top">http://pdos.csail.mit.edu/~baford/packrat/popl04/</a>
- </p></div>
- <div id="ftn.spirit_x3.abstracts.syntax_diagram.f1" class="footnote"><p><a href="#spirit_x3.abstracts.syntax_diagram.f1" class="para"><sup class="para">[3] </sup></a>
- Richard E. Pattis: EBNF: A Notation to Describe Syntax, <a href="http://www.cs.cmu.edu/~pattis/misc/ebnf.pdf" target="_top">http://www.cs.cmu.edu/~pattis/misc/ebnf.pdf</a>
- </p></div>
- <div id="ftn.spirit_x3.abstracts.syntax_diagram.f2" class="footnote"><p><a href="#spirit_x3.abstracts.syntax_diagram.f2" class="para"><sup class="para">[4] </sup></a>
- Niklaus Wirth: The Programming Language Pascal. (July 1973)
- </p></div>
- </div>
- </div>
- <table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr>
- <td align="left"></td>
- <td align="right"><div class="copyright-footer">Copyright © 2001-2018 Joel de Guzman,
- Hartmut Kaiser<p>
- Distributed under the Boost Software License, Version 1.0. (See accompanying
- file LICENSE_1_0.txt or copy at <a href="http://www.boost.org/LICENSE_1_0.txt" target="_top">http://www.boost.org/LICENSE_1_0.txt</a>)
- </p>
- </div></td>
- </tr></table>
- <hr>
- <div class="spirit-nav">
- <a accesskey="p" href="../abstracts.html"><img src="../../../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../abstracts.html"><img src="../../../../../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../../index.html"><img src="../../../../../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="parsing_expression_grammar.html"><img src="../../../../../../../doc/src/images/next.png" alt="Next"></a>
- </div>
- </body>
- </html>
|