Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <h2>The 10,000ft overview</h2> <p>You need to do this with a small custom parser: code takes input of this form and transforms it to the form you want.</p> <p>In practice I find it useful to group parsing problems like this in one of three categories based on their complexity:</p> <ol> <li><strong>Trivial:</strong> Problems that can be solved with a few loops and humane regular expressions. This category is seductive: if you are even a little unsure if the problem can be solved this way, a good rule of thumb is to decide that it cannot.</li> <li><strong>Easy:</strong> Problems that require building a small parser yourself, but are still simple enough that it doesn't quite make sense to bring out the big guns. If you need to write more than ~100 lines of code then consider escalating to the next category.</li> <li><strong>Involved:</strong> Problems for which it makes sense to go formal and use an already existing, proven parser generator¹.</li> </ol> <p>I classify this particular problem as belonging into the second category, which means that you can approach it like this:</p> <h2>Writing a small parser</h2> <h3>Defining the grammar</h3> <p>To do this, you must first define -- at least informally, with a few quick notes -- the <em>grammar</em> that you want to parse. Keep in mind that most grammars are defined recursively at some point. So let's say our grammar is:</p> <ul> <li>The input is a <em>sequence</em></li> <li>A <em>sequence</em> is a series series of zero or more <em>tokens</em></li> <li>A token is either a <em>word</em>, a <em>string</em> or an <em>array</em></li> <li>Tokens are separated by one or more whitespace characters</li> <li>A <em>word</em> is a sequence of alphabetic characters (a-z)</li> <li>A <em>string</em> is an arbitrary sequence of characters enclosed within double quotes</li> <li>An <em>array</em> is a series of one or more <em>tokens</em> separated by <em>commas</em></li> </ul> <p>You can see that we have recursion in one place: a sequence can contain arrays, and an array is also defined in terms of a sequence (so it can contain more arrays etc).</p> <p>Treating the matter informally as above is easier as an introduction, but reasoning about grammars is easier if you do it <a href="http://en.wikipedia.org/wiki/Formal_grammar" rel="nofollow noreferrer">formally</a>.</p> <h3>Building a lexer</h3> <p>With the grammar in hand you know need to break the input down into tokens so that it can be processed. The component that takes user input and converts it to individual pieces defined by the grammar is called a <em><a href="http://en.wikipedia.org/wiki/Lexical_analysis" rel="nofollow noreferrer">lexer</a></em>. Lexers are dumb; they are only concerned with the "outside appearance" of the input and do not attempt to check that it actually makes sense.</p> <p>Here's a simple lexer I wrote to parse the above grammar (don't use this for anything important; may contain bugs):</p> <pre><code>$input = 'all ("hi there", (this, that) , other) another'; $tokens = array(); $input = trim($input); while($input) { switch (substr($input, 0, 1)) { case '"': if (!preg_match('/^"([^"]*)"(.*)$/', $input, $matches)) { die; // TODO: error: unterminated string } $tokens[] = array('string', $matches[1]); $input = $matches[2]; break; case '(': $tokens[] = array('open', null); $input = substr($input, 1); break; case ')': $tokens[] = array('close', null); $input = substr($input, 1); break; case ',': $tokens[] = array('comma', null); $input = substr($input, 1); break; default: list($word, $input) = array_pad( preg_split('/(?=[^a-zA-Z])/', $input, 2), 2, null); $tokens[] = array('word', $word); break; } $input = trim($input); } print_r($tokens); </code></pre> <h3>Building a parser</h3> <p>Having done this, the next step is to build a <em><a href="http://en.wikipedia.org/wiki/Parser" rel="nofollow noreferrer">parser</a></em>: a component that inspects the lexed input and converts it to the desired format. A parser is smart; in the process of converting the input it also makes sure that the input is well-formed by the grammar's rules.</p> <p>Parsers are commonly implemented as <a href="http://en.wikipedia.org/wiki/Finite-state_machine" rel="nofollow noreferrer">state machines</a> (also known as finite state machines or finite automata) and work like this:</p> <ul> <li>The parser has a <em>state</em>; this is usually a number in an appropriate range, but each state is also described with a more human-friendly name.</li> <li>There is a loop that reads reads lexed tokens one at a time. Based on the current state and the value of the token, the parser may decide to do one or more of the following: <ol> <li>take some action that affects its output</li> <li>change its state to some other value</li> <li>decide that the input is badly formed and produce an error</li> </ol></li> </ul> <hr> <p>¹ Parser generators are programs whose input is a formal grammar and whose output is a lexer and a parser you can "just add water" to: just extend the code to perform "take some action" depending on the type of token; everything else is already taken care of. A quick search on this subject gives led <a href="https://stackoverflow.com/questions/8002617/php-lexer-and-parser-generator">PHP Lexer and Parser Generator?</a></p>
    singulars
    1. This table or related slice is empty.
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. VO
      singulars
      1. This table or related slice is empty.
    2. VO
      singulars
      1. This table or related slice is empty.
    3. VO
      singulars
      1. This table or related slice is empty.
 

Querying!

 
Guidance

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload