How To Write A Simple Lexical Analyzer or Parser - Revision history

SeanParent at 20:26, 20 October 2011

2011-10-20T20:26:25Z

SeanParent: /* A Simple Recursive Decent Parser */

2008-05-20T17:25:05Z

‎A Simple Recursive Decent Parser

SeanParent: /* A Simple Recursive Decent Parser */

2008-05-20T17:16:37Z

‎A Simple Recursive Decent Parser

SeanParent: /* A Simple Recursive Decent Parser */

2008-05-20T17:16:03Z

‎A Simple Recursive Decent Parser

SeanParent: /* Introduction */

2008-05-20T17:14:50Z

‎Introduction

SeanParent: /* A Simple Recursive Decent Parser */

2008-05-03T00:19:49Z

‎A Simple Recursive Decent Parser

SeanParent: /* A Simple Recursive Decent Parser */

2008-05-03T00:18:31Z

‎A Simple Recursive Decent Parser

SeanParent: /* A Simple Recursive Decent Parser */

2008-05-03T00:17:38Z

‎A Simple Recursive Decent Parser

SeanParent: /* A Simple Recursive Decent Parser */

2008-05-03T00:12:59Z

‎A Simple Recursive Decent Parser

Show changes

SeanParent: /* Introduction */

2008-05-02T23:34:56Z

‎Introduction

@@ Line 28: / Line 28: @@
 template <typename I> // I models InputIterator
 // require value_type(I) == code_point_t
      bool is_production(T& value);
@@ Line 194: / Line 196: @@
 That's the complete code. Besides having a solution to our problem we have a general framework for building other solutions to parsing problems and a pretty decent start that can be reused for other XML related issues. Parsers written in this style are simple to extend even if they are packaged as a library, you can simply inherit from the struct and add additional productions. The code described here took very little time to write (the biggest hassle was building the larger lookup tables from the productions in the XML specification.
-The complete example file can be found [http://stlab.adobe.com:8080/@md=d&cd=//sandbox/papers/xml_parser_example/&cdf=//sandbox/papers/xml_parser_example/xml_parser_example.cpp&c=9XT@//sandbox/papers/xml_parser_example/xml_parser_example.cpp?ac=64&rev1=2 here.]
+The complete example file can be found [http://stlab.adobe.com:8080/sandbox/papers/xml_parser_example/xml_parser_example.cpp?ac=64&rev1=3 here.]

@@ Line 17: / Line 17: @@
 </pre>
-The stream denoted by first last is going to be UTF16 code points because that is how the XML specification is defined. We'll define code_point_t to be a 16 bit integer:
+The stream denoted by <tt>[first, last)</tt> is going to be UTF16 code points because that is how the XML specification is defined. We'll define code_point_t to be a 16 bit integer:
 <pre>
@@ Line 35: / Line 35: @@
 </pre>
-Writing the body of the production is generally quite simple. We start at the top level production rule and work our way down - in this case we are interested in parsing <tt>Name</tt>. The <tt>Name</tt> production rule looks like this:
+Writing the body of the production is simple. We start at the top level production rule and work our way down - in this case we are interested in parsing <tt>Name</tt>. The <tt>Name</tt> production rule looks like this:
 <pre>
@@ Line 62: / Line 62: @@
 </pre>
-Here string16_t is our token type. For this problem, we don't actually care what the token value is - and constructing the token is relatively expensive (if we were writing a full-blown XML parser we would spend some energy on dealing with tokens efficiently. This code also doesn't tell is if the name is qualified or reserved - those are attributes of our token value. So we're going to rewrite the function to drop the token and add some attributes. We'll deal with attributes in a similar fashion to the value of the production rule, except if the production rule is recognized the attributes will be accumulated (as opposed to overwritten). We don't need to pass the attribute to all production rules, only those that have attributes. Here is the definition of our attribute type:
+Here string16_t is our token type. For this problem, we don't actually care what the token value is - and constructing the token is relatively expensive. If we were writing a full-blown XML parser we would spend some energy on dealing with tokens efficiently. This code also doesn't tell is if the name is qualified or reserved - those are attributes of our token value. We rewrite the function to drop the token and add some attributes. We'll deal with attributes in a similar fashion to the value of the production rule, except if the production rule is recognized the attributes will be accumulated (as opposed to overwritten). We don't need to pass the attribute to all production rules, only those that have attributes. Here is the definition of our attribute type:
 <pre>
@@ Line 145: / Line 145: @@
 </pre>
-Some of the tables, such as the one for <tt>BaseChar</tt> are quite large making it prohibitively expensive to write an expression like <tt>(0x4E00U <= x && x <= 0x9FA5U) || (x == 0x3007U) || ...</tt>. Instead we will create a simple lookup table. When dealing with a parser that works with a simple <tt>char</tt> type we could just build a table with 256 elements that contained an enumeration indicating what production rule the character matched. A table 16 bit values would be a bit large (but we could do it - 64K elements) - but instead we'll create an array of values denoting ranges which contain the code points we want to match and search to find if our character is in one of the ranges. To do that we'll create a semi-open ranges for each character range of the form <tt>(f0, l0], (f1, l1], ...</tt> and then use <tt>lower_bound()</tt> to search the table, if we end up on an odd index (starting at 0) then the item is in the range, an even index it is not. This strategy means we can't represent a range which includes <tt>0</tt> but <tt>0</tt> is not a valid character in an XML production. The code for the table lookup for <tt>Ideographic</tt> is this:
+Some of the tables, such as the one for <tt>BaseChar</tt> are quite large making it prohibitively expensive to write an expression like <tt>(0x4E00U <= x && x <= 0x9FA5U) || (x == 0x3007U) || ...</tt>. Instead we will create a simple lookup table. When dealing with a parser that works with a simple <tt>char</tt> type we could just build a table with 256 elements that contained an enumeration indicating what production rule the character matched. A table of 16 bit values would be a bit large (but we could do it - 64K elements) - but instead we'll create an array of values denoting ranges which contain the code points we want to match and search to find if our character is in one of the ranges. To do that we'll create a semi-open ranges for each character range of the form <tt>(f0, l0], (f1, l1], ...</tt> and then use <tt>lower_bound()</tt> to search the table, if we end up on an odd index (starting at 0) then the item is in the range, an even index it is not. This strategy means we can't represent a range which includes <tt>0</tt> but <tt>0</tt> is not a valid character in an XML production. The code for the table lookup for <tt>Ideographic</tt> is this:
 <pre>
@@ Line 161: / Line 161: @@
 </pre>
-To transform from the closed ranges to the semi-open ranges we subtract one from the first item in the range. Note that this code doesn't have to be a member function and is not a template - we can put these lookup tables in a .cpp file. We'll use this function in our <tt>is_ideographic()</tt> member function:
+To transform from the closed ranges to the semi-open ranges we subtract one from the first item in the range. This code doesn't have to be a member function and is not a template - we can put these lookup tables in a .cpp file. We'll use this function in our <tt>is_ideographic()</tt> member function:
 <pre>
@@ Line 192: / Line 192: @@
 </pre>
-That's the complete code. Besides having a solution to our problem we also have a general framework for building other solutions to parsing problems and a pretty decent start that can be reused for other XML related issues. Parsers written in this style are simple to extend even if they are packaged as a library, you can simply inherit from the struct and add additional productions. The code described here took very little time to write (the biggest hassle was building the larger lookup tables from the productions in the XML specification.
+That's the complete code. Besides having a solution to our problem we have a general framework for building other solutions to parsing problems and a pretty decent start that can be reused for other XML related issues. Parsers written in this style are simple to extend even if they are packaged as a library, you can simply inherit from the struct and add additional productions. The code described here took very little time to write (the biggest hassle was building the larger lookup tables from the productions in the XML specification.
 The complete example file can be found [http://stlab.adobe.com:8080/@md=d&cd=//sandbox/papers/xml_parser_example/&cdf=//sandbox/papers/xml_parser_example/xml_parser_example.cpp&c=9XT@//sandbox/papers/xml_parser_example/xml_parser_example.cpp?ac=64&rev1=2 here.]

@@ Line 9: / Line 9: @@
 == A Simple Recursive Decent Parser ==
-To solve the problem of validating an XML name we're going to write a simple recursive decent, or top-down, parser. The idea is to read from a stream of characters denoted by a pair of InputIterators - we will only need to read each character once without backtracking (a grammar which can be read without backtracking is known as an [http://en.wikipedia.org/wiki/LL_parser LL(1)] grammar.
+To solve the problem of validating an XML name we're going to write a simple recursive decent, or top-down, parser. The idea is to read from a stream of characters denoted by a pair of InputIterators - we will only need to read each character once without backtracking. A grammar which can be read in this form without backtracking is known as an [http://en.wikipedia.org/wiki/LL_parser LL(1)] grammar.
 To do this we are going to translate each production rule into a function which will return a <tt>bool</tt> with the value <tt>true</tt> if it recognizes the production and false if it does not. If it does recognize the production then the stream will be advanced to the end of the production and a value will be updated with the recognized production. Otherwise, the stream and value are left unchanged. Such a function will follow this pattern:

@@ Line 9: / Line 9: @@
 == A Simple Recursive Decent Parser ==
-To solve the problem of validating an XML name we're going to write a simple recursive decent, or top-down, parser. The idea is to read from a stream of character denoted by a pair of InputIterators - we will only need to read each character once without backtracking (a grammar which can be read without backtracking is known as an [http://en.wikipedia.org/wiki/LL_parser LL(1)] grammar.
+To solve the problem of validating an XML name we're going to write a simple recursive decent, or top-down, parser. The idea is to read from a stream of characters denoted by a pair of InputIterators - we will only need to read each character once without backtracking (a grammar which can be read without backtracking is known as an [http://en.wikipedia.org/wiki/LL_parser LL(1)] grammar.
 To do this we are going to translate each production rule into a function which will return a <tt>bool</tt> with the value <tt>true</tt> if it recognizes the production and false if it does not. If it does recognize the production then the stream will be advanced to the end of the production and a value will be updated with the recognized production. Otherwise, the stream and value are left unchanged. Such a function will follow this pattern:

@@ Line 3: / Line 3: @@
 This ''paper'' is a response to an e-mail question asking if anyone had code to validate that a sequence of characters was a valid XML name which was not a reserved XML name (starting with <tt>'x'|'X' 'm'|'M' 'l'|'L'</tt>) or a qualified name (one containing <tt>':'</tt>). ''See [http://www.w3.org/TR/REC-xml/#sec-common-syn Section 2.3 of the XML Specification].''
-Languages are defined using a grammar. There are many notations for grammars but most use some variant of [http://en.wikipedia.org/wiki/Extended_Backus–Naur_form Extended Backus-Naur form] (EBNF), XML is no exception to this rule. The variant of EBNF used for the XML notation is described in [http://www.w3.org/TR/REC-xml/#sec-notation Section 6 of the XML Specification]. Transforming an EBNF grammar into a lexical analyzer and/or parser is a relatively straight forward process. For simplicity I define the lexical analyzer as the system which transforms a stream of characters into tokens and the parser as the system which reads the tokens and takes invokes some semantic action for the production rules. There are libraries, such as the [http://www.boost.org/doc/libs/1_35_0/libs/spirit/index.html Boost Spirit Library] and tools such as [http://en.wikipedia.org/wiki/Lex_programming_tool Lex] and [http://en.wikipedia.org/wiki/Yacc Yacc] which can be used to aid in writing lexical analyzers and parser. Knowing how to write these systems simply and directly is an invaluable tool in any programmers tool chest and experience with writing such systems will make you more productive when using libraries and tools and give you some insight into when you should and should not use them. Some issues (including this one) can also be addressed by writing a regular expression using a library such as the [http://www.boost.org/doc/libs/1_35_0/libs/regex/doc/html/index.html Boost Regex Library] - however, dealing with the numerous ranges of values in the grammar production with this problem are difficult to express in a regular expression. A [http://en.wikipedia.org/wiki/Finite_state_machine finite automata] can also be constructed for many such problems (including this one) and such systems have the advantage of inverting control flow - you put values into a finite automata as opposed to executing a parse function which pulls values from a stream.
+Languages are defined using a grammar. There are many notations for grammars but most use some variant of [http://en.wikipedia.org/wiki/Extended_Backus–Naur_form Extended Backus-Naur form] (EBNF), XML is no exception to this rule. The variant of EBNF used for the XML notation is described in [http://www.w3.org/TR/REC-xml/#sec-notation Section 6 of the XML Specification]. Transforming an EBNF grammar into a lexical analyzer and/or parser is a relatively straight forward process. For simplicity I define the lexical analyzer as the system which transforms a stream of characters into tokens and the parser as the system which transforms a stream of tokens into a sequence of actions for each production rule. There are libraries, such as the [http://www.boost.org/doc/libs/1_35_0/libs/spirit/index.html Boost Spirit Library] and tools such as [http://en.wikipedia.org/wiki/Lex_programming_tool Lex] and [http://en.wikipedia.org/wiki/Yacc Yacc] which can be used to aid in writing lexical analyzers and parser. Knowing how to write these systems simply and directly is an invaluable tool in any programmers tool chest and experience with writing such systems will make you more productive when using libraries and tools and give you some insight into when you should and should not use them. Some issues (including this one) can also be addressed by writing a regular expression using a library such as the [http://www.boost.org/doc/libs/1_35_0/libs/regex/doc/html/index.html Boost Regex Library] - however, dealing with the numerous ranges of values in the grammar production with this problem are difficult to express in a regular expression. A [http://en.wikipedia.org/wiki/Finite_state_machine finite automata] can also be constructed for many such problems (including this one) and such systems have the advantage of inverting control flow - you put values into a finite automata as opposed to executing a parse function which pulls values from a stream.
 When you look at a typical EBNF grammar it will frequently not distinguish which parts are the lexical analyzer production rules and which are the parser production rules - the structure of both a simple parser and simple lexer will be the same. The separation is the point where the value returned by the production rule is not a character from the stream, but some form of token. Because the structure is the same I'm going to refer from here on to both parts as simply the ''parser''.

@@ Line 103: / Line 103: @@
 <pre>
-NameChar  ::=  Letter | Digit | '.' | '-' | '_' | ':' | CombiningChar | Extender
+NameChar ::= Letter | Digit | '.' | '-' | '_' | ':' | CombiningChar | Extender
 </pre>

@@ Line 142: / Line 142: @@
 <pre>
-Ideographic  ::= 	[#x4E00-#x9FA5] | #x3007 | [#x3021-#x3029]
+Ideographic ::= [#x4E00-#x9FA5] | #x3007 | [#x3021-#x3029]
 </pre>

@@ Line 121: / Line 121: @@
 <pre>
-Letter  ::= BaseChar | Ideographic
+Letter ::= BaseChar | Ideographic
 </pre>
 <pre>