Codebase list ohcount / d62f219c-a984-415f-b69c-f521b00b8f15/main doc / html / parser_doc.html
d62f219c-a984-415f-b69c-f521b00b8f15/main

Tree @d62f219c-a984-415f-b69c-f521b00b8f15/main (Download .tar.gz)

parser_doc.html @d62f219c-a984-415f-b69c-f521b00b8f15/mainraw · history · blame

<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html><head><meta http-equiv="Content-Type" content="text/html;charset=UTF-8">
<title>ohcount: Parser Documentation</title>
<link href="tabs.css" rel="stylesheet" type="text/css">
<link href="doxygen.css" rel="stylesheet" type="text/css">
</head><body>
<!-- Generated by Doxygen 1.5.9 -->
<div class="navigation" id="top">
  <div class="tabs">
    <ul>
      <li><a href="index.html"><span>Main&nbsp;Page</span></a></li>
      <li class="current"><a href="pages.html"><span>Related&nbsp;Pages</span></a></li>
      <li><a href="annotated.html"><span>Data&nbsp;Structures</span></a></li>
      <li><a href="files.html"><span>Files</span></a></li>
    </ul>
  </div>
</div>
<div class="contents">
<h1><a class="anchor" name="parser_doc">Parser Documentation </a></h1><dl class="author" compact><dt><b>Author:</b></dt><dd>Mitchell Foral</dd></dl>
<h2><a class="anchor" name="overview">
Overview</a></h2>
I will assume the reader has a decent knowledge of how Ragel works and the Ragel syntax. If not, please review the Ragel manual found at: <a href="http://research.cs.queensu.ca/~thurston/ragel/">http://research.cs.queensu.ca/~thurston/ragel/</a><p>
All parsers must at least:<p>
<ul>
<li>Call a callback function when a line of code is parsed. </li>
<li>Call a callback function when a line of comment is parsed. </li>
<li>Call a callback function when a blank line is parsed.</li>
</ul>
Additionally a parser can call the callback function for each position of entities parsed.<p>
Take a look at 'c.rl' and even keep it open for reference when reading this document to better understand how parsers work and how to write one.<h2><a class="anchor" name="writing">
Writing a Parser</a></h2>
First create your parser in 'src/parsers/'. Its name should be the language you are parsing with a '.rl' extension. You will not have to manually compile any parsers, as this is automatically for you. However, you do need to add your parser to 'hash/parsers.gperf'.<p>
Every parser must have the following at the top:<p>
<div class="fragment"><pre class="fragment"><span class="comment">/************************* Required for every parser *************************/</span>
<span class="preprocessor">#ifndef OHCOUNT_C_PARSER_H</span>
<span class="preprocessor"></span><span class="preprocessor">#define OHCOUNT_C_PARSER_H</span>
<span class="preprocessor"></span>
<span class="preprocessor">#include "../parser_macros.h"</span>

<span class="comment">// the name of the language</span>
<span class="keyword">const</span> <span class="keywordtype">char</span> *C_LANG = <a class="code" href="languages_8h.html#69f1d54d0578e6b3400b774500973439">LANG_C</a>;

<span class="comment">// the languages entities</span>
<span class="keyword">const</span> <span class="keywordtype">char</span> *c_entities[] = {
  <span class="stringliteral">"space"</span>, <span class="stringliteral">"comment"</span>, <span class="stringliteral">"string"</span>, <span class="stringliteral">"number"</span>, <span class="stringliteral">"preproc"</span>,
  <span class="stringliteral">"keyword"</span>, <span class="stringliteral">"identifier"</span>, <span class="stringliteral">"operator"</span>, <span class="stringliteral">"any"</span>
};

<span class="comment">// constants associated with the entities</span>
<span class="keyword">enum</span> {
  C_SPACE = 0, C_COMMENT, C_STRING, C_NUMBER, C_PREPROC,
  C_KEYWORD, C_IDENTIFIER, C_OPERATOR, C_ANY
};

<span class="comment">/*****************************************************************************/</span>
</pre></div><p>
And the following at the bottom:<p>
<div class="fragment"><pre class="fragment"><span class="comment">/************************* Required for every parser *************************/</span>

<span class="comment">/* Parses a string buffer with C/C++ code.</span>
<span class="comment"> *</span>
<span class="comment"> * @param *buffer The string to parse.</span>
<span class="comment"> * @param length The length of the string to parse.</span>
<span class="comment"> * @param count Integer flag specifying whether or not to count lines. If yes,</span>
<span class="comment"> *   uses the Ragel machine optimized for counting. Otherwise uses the Ragel</span>
<span class="comment"> *   machine optimized for returning entity positions.</span>
<span class="comment"> * @param *callback Callback function. If count is set, callback is called for</span>
<span class="comment"> *   every line of code, comment, or blank with 'lcode', 'lcomment', and</span>
<span class="comment"> *   'lblank' respectively. Otherwise callback is called for each entity found.</span>
<span class="comment"> */</span>
<span class="keywordtype">void</span> parse_c(<span class="keywordtype">char</span> *buffer, <span class="keywordtype">int</span> length, <span class="keywordtype">int</span> count,
             <span class="keywordtype">void</span> (*callback) (<span class="keyword">const</span> <span class="keywordtype">char</span> *lang, <span class="keyword">const</span> <span class="keywordtype">char</span> *<a class="code" href="parser__macros_8h.html#d4e4601988acb4a95ecd1ec380359ae5">entity</a>, <span class="keywordtype">int</span> s,
                               <span class="keywordtype">int</span> e, <span class="keywordtype">void</span> *udata),
             <span class="keywordtype">void</span> *userdata
  ) {
  <a class="code" href="parser__macros_8h.html#c1af3f499e72dfc161f2fce616dfd8e7">init</a>

  %% write <a class="code" href="parser__macros_8h.html#c1af3f499e72dfc161f2fce616dfd8e7">init</a>;
  <a class="code" href="parser__macros_8h.html#d35c7ed2784f4fb57849237ce534f17e">cs</a> = (count) ? c_en_c_line : c_en_c_entity;
  %% write exec;

  <span class="comment">// if no newline at EOF; callback contents of last line</span>
  <span class="keywordflow">if</span> (count) { <a class="code" href="parser__macros_8h.html#1adf47f60e418da0f0c3caa471728021">process_last_line</a>(C_LANG) }
}

<span class="preprocessor">#endif</span>
<span class="preprocessor"></span>
<span class="comment">/*****************************************************************************/</span>
</pre></div><p>
(Your parser will go between these two blocks.)<p>
The code can be found in the existing 'c.rl' parser. You will need to change: <ul>
<li>OHCOUNT_[lang]_PARSER_H - Replace [lang] with your language name. So if you are writing a C parser, it would be OHCOUNT_C_PARSER_H. </li>
<li>[lang]_LANG - Set the variable name to be [lang]_LANG and its value to be the name of your language to parse as defined in <a class="el" href="languages_8h.html">languages.h</a>. [lang] is your language name. For C it would be C_LANG. </li>
<li>[lang]_entities - Set the variable name to be [lang]_entities (e.g. c_entries) The value is an array of string entities your language has. For example C has comment, string, number, etc. entities. You should definately have "space", and "any" entities. "any" entities are typically used for entity machines (discussed later) and match any character that is not recognized so the parser does not do something unpredictable. </li>
<li>enum - Change the value of the enum to correspond with your entities. So if in your parser you look up [lang]_entities[ENTITY], you will get the associated entity's string name. </li>
<li>parse_[lang] - Set the function name to parse_[lang] where again, [lang] is the name of your language. In the case of C, it is parse_c. </li>
<li>[lang]_en_[lang]_line - The line counting machine. </li>
<li>[lang]_en_[lang]_entity - The entity machine.</li>
</ul>
You may be asking why you have to rename variables and functions. Well if variables have the same name in header files (which is what parsers are), the compiler complains. Also, when you have languages embedded inside each other, any identifiers with the same name can easily be mixed up. It is also important to prefix your Ragel definitions with your language to avoid conflicts with other parsers.<p>
Additional variables available to parsers are in the <a class="el" href="parser__macros_8h.html">parser_macros.h</a> file. Take a look at it and try to understand what the variables are used for. They will make more sense later on.<p>
Now you can define your Ragel parser. Name your machine after your language, "write data", and include 'common.rl', a file with common Ragel definitions, actions, etc. For example:<p>
<div class="fragment"><pre class="fragment">%%{
  machine c;
  write data;
  include <span class="stringliteral">"common.rl"</span>;

  ...
}%%
</pre></div><p>
Before you begin to write patterns for each entity in your language, you need to understand how the parser should work.<p>
Each parser has two machines: one optimized for counting lines of code, comments, and blanks; the other for identifying entity positions in the buffer.<h2><a class="anchor" name="line">
Line Counting Machine</a></h2>
This machine should be written as a line-by-line parser for multiple lines. This means you match any combination of entities except a newline up until you do reach a newline. If the line contains only spaces, or nothing at all, it is blank. If the line contains spaces at first, but then a comment, or just simply a comment, the line is a comment. If the line contains anything but a comment after spaces (if there are any), it is a line of code. You will do this using a Ragel scanner. The callback function will be called for each line parsed.<h3><a class="anchor" name="line_scanner">
Scanner Parser Structure</a></h3>
A scanner parser will look like this:<p>
<div class="fragment"><pre class="fragment">[lang]_line := |*
  entity1 ${ entity = ENTITY1; } =&gt; [lang]_ccallback;
  entity2 ${ entity = ENTITY2; } =&gt; [lang]_ccallback;
  ...
  entityn ${ entity = ENTITYN; } =&gt; [lang]_ccallback;
*|;
</pre></div><p>
(As usual, replace [lang] with your language name.)<p>
Each entity is the pattern for an entity to match, the last one typically being the newline entity. For each match, the variable is set to a constant defined in the enum, and the main action is called (you will need to create this action above the scanner).<p>
When you detect whether or not a line is code or comment, you should call the appropriate @code or @comment action defined in 'common.rl' as soon as possible. It is not necessary to worry about whether or not these actions are called more than once for a given line; the first call to either sets the status of the line permanently. Sometimes you cannot call @code or @comment for one reason or another. Do not worry, as this is discussed later.<p>
When you reach a newline, you will need to decide whether the current line is a line of code, comment, or blank. This is easy. Simply check if the <a class="el" href="parser__macros_8h.html#6c107b5ead58c230e358212891737cc3">line_contains_code</a> or <a class="el" href="parser__macros_8h.html#6610fa10e2ad8df10bb6e04babf0bbd8">whole_line_comment</a> variables are set to 1. If neither of them are, the line is blank. Then call the callback function (not action) with an "lcode", "lcomment", or "lblank" string, and the start and end positions of that line (including the newline). The start position of the line is in the <a class="el" href="parser__macros_8h.html#6f5b3cc3254a82d5d28a418a40f59272">line_start</a> variable. It should be set at the beginning of every line either through the @code or @comment actions, or manually in the main action. Finally the <a class="el" href="parser__macros_8h.html#6c107b5ead58c230e358212891737cc3">line_contains_code</a>, <a class="el" href="parser__macros_8h.html#6610fa10e2ad8df10bb6e04babf0bbd8">whole_line_comment</a>, and <a class="el" href="parser__macros_8h.html#6f5b3cc3254a82d5d28a418a40f59272">line_start</a> state variables must be reset. All this should be done within the main action shown below. Note: For most parsers, the <a class="el" href="parser__macros_8h.html#aaf8abebfd56b683567c15bfa3f063f1">std_newline(lang)</a> macro is sufficient and does everything in the main action mentioned above. The lang parameter is the [lang]_LANG string.<h3><a class="anchor" name="line_action">
Main Action Structure</a></h3>
The main action looks like this:<p>
<div class="fragment"><pre class="fragment">action [lang]_ccallback {
  <span class="keywordflow">switch</span>(entity) {
  when ENTITY1:
    ...
    <span class="keywordflow">break</span>;
  when ENTITY2:
    ...
    <span class="keywordflow">break</span>;
  ...
  when ENTITYN:
    ...
    <span class="keywordflow">break</span>;
  }
}
</pre></div><h3><a class="anchor" name="line_entity_patterns">
Defining Patterns for Entities</a></h3>
Now it is time to write patterns for each entity in your language. That does not seem very hard, except when your entity can cover multiple lines. Comments and strings in particular can do this. To make an accurate line counter, you will need to count the lines covered by multi-line entities. When you detect a newline inside your multi-line entity, you should set the entity variable to be <a class="el" href="parser__macros_8h.html#7e82c89c9a3dc533077791088d1ee77b">INTERNAL_NL</a> and call the main action. The main action should have a case for <a class="el" href="parser__macros_8h.html#7e82c89c9a3dc533077791088d1ee77b">INTERNAL_NL</a> separate from the newline entity. In it, you will check if the current line is code or comment and call the callback function with the appropriate string ("lcode" or "lcomment") and beginning and end of the line (including the newline). Afterwards, you will reset the <a class="el" href="parser__macros_8h.html#6c107b5ead58c230e358212891737cc3">line_contains_code</a> and <a class="el" href="parser__macros_8h.html#6610fa10e2ad8df10bb6e04babf0bbd8">whole_line_comment</a> state variables. Then set the <a class="el" href="parser__macros_8h.html#6f5b3cc3254a82d5d28a418a40f59272">line_start</a> variable to be <a class="el" href="parser__macros_8h.html#aa1ebe818ec1c763a776cc580551f3e6">p</a>, the current Ragel buffer position. Because <a class="el" href="parser__macros_8h.html#6c107b5ead58c230e358212891737cc3">line_contains_code</a> and <a class="el" href="parser__macros_8h.html#6610fa10e2ad8df10bb6e04babf0bbd8">whole_line_comment</a> have been reset, any non-newline and non-space character in the multi-line pattern should set <a class="el" href="parser__macros_8h.html#6c107b5ead58c230e358212891737cc3">line_contains_code</a> or <a class="el" href="parser__macros_8h.html#6610fa10e2ad8df10bb6e04babf0bbd8">whole_line_comment</a> back to 1. Otherwise you would count the line as blank.<p>
Note: For most parsers, the <a class="el" href="parser__macros_8h.html#b08c3ed468f4ad3e1a9d391c1a4337d0">std_internal_newline(lang)</a> macro is sufficient and does everything in the main action mentioned above. The lang parameter is the [lang]_LANG string.<p>
For multi-line matches, it is important to call the @code or @comment actions (mentioned earlier) before an internal newline is detected so the <a class="el" href="parser__macros_8h.html#6c107b5ead58c230e358212891737cc3">line_contains_code</a> and <a class="el" href="parser__macros_8h.html#6610fa10e2ad8df10bb6e04babf0bbd8">whole_line_comment</a> variables are properly set. For other entities, you can use the <a class="el" href="parser__macros_8h.html#814f6dab3b0678113d97a3684282934a">code</a> macro inside the main action which executes the same code as the Ragel @code action. Other C macros are <a class="el" href="parser__macros_8h.html#43be22b7a1b528eaf759e034ec581543">comment</a> and <a class="el" href="parser__macros_8h.html#a4df6978a0e35c95ca051f1da0dd7e86">ls</a>, the latter is typically used for the SPACE entity when defining <a class="el" href="parser__macros_8h.html#6f5b3cc3254a82d5d28a418a40f59272">line_start</a>.<p>
Also for multi-line matches, it may be necessary to use the @enqueue and @commit actions. If it is possible that a multi-line entity will not have an ending delimiter (for example a string), use the @enqueue action as soon as the start delimitter has been detected, and the @commit action as soon as the end delimitter has been detected. This will eliminate the potential for any counting errors.<h3><a class="anchor" name="line_notes">
Notes</a></h3>
You can be a bit sloppy with the line counting machine. For example the only C entities that can contain newlines are strings and comments, so <a class="el" href="parser__macros_8h.html#7e82c89c9a3dc533077791088d1ee77b">INTERNAL_NL</a> would only be necessary inside them. Other than those, anything other than spaces is considered code, so do not waste your time defining specific patterns for other entities.<h3><a class="anchor" name="line_embedded">
Parsers with Embedded Languages</a></h3>
Notation: [lang] is the parent language, [elang] is the embedded language.<p>
To write a parser with embedded languages (such as HTML with embedded CSS and Javascript), you should first #include the parser(s) above your Ragel code. The header file is "[elang]_parser.h".<p>
Next, after the inclusion of 'common.rl', add "#EMBED([elang])" on separate lines for each embedded language. The build process looks for these special comments to embed the language for you automatically.<p>
In your main action, you need to add another entity <a class="el" href="parser__macros_8h.html#a48fd5c8dbc18cdf9daaa5810227f829">CHECK_BLANK_ENTRY</a>. It should call the <a class="el" href="parser__macros_8h.html#dcdd4261cb35490ebe8f88afd0b4787c">check_blank_entry</a>([lang]_LANG) macro. Blank entries are an entry into an embedded language, but the rest of the line is blank before a newline. For example, a CSS entry in HTML is something like:<p>
<div class="fragment"><pre class="fragment">   &lt;style type=<span class="stringliteral">"text/css"</span>&gt;
</pre></div><p>
If there is no CSS code after the entry (a blank entry), the line should be counted as HTML code, and the <a class="el" href="parser__macros_8h.html#dcdd4261cb35490ebe8f88afd0b4787c">check_blank_entry</a> macro handles this. But you may be asking, "how do I get to the CHECK_BLANK_ENTRY entity?". This will be discussed in just a bit.<p>
The <a class="el" href="parser__macros_8h.html#b5304b201ce6824e3c021e245d6a5e94">emb_newline</a> and <a class="el" href="parser__macros_8h.html#2822d59197758531b6f4a0cc13d0257b">emb_internal_newline</a> macros should be used instead of the <a class="el" href="parser__macros_8h.html#aaf8abebfd56b683567c15bfa3f063f1">std_newline</a> and <a class="el" href="parser__macros_8h.html#b08c3ed468f4ad3e1a9d391c1a4337d0">std_internal_newline</a> macros.<p>
For each embedded language you will have to define an entry and outry. An entry is the pattern that transitions from the parent language into the child language. An outry is the pattern from child to parent. You will need to put your entries in your [lang]_line machine. You will also need to re-create each embedded language's line machine (define as [lang]_[elang]_line; e.g. html_css_line) and put outry patterns in those. Entries typically would be defined as [lang]_[elang]_entry, and outries as [lang]_[elang]_outry.<p>
Note: An outry should have a @check_blank_outry action so the line is not mistakenly counted as a line of embedded language code if it is actually a line of parent code.<h3><a class="anchor" name="line_entry_action">
Entry Pattern Actions</a></h3>
<div class="fragment"><pre class="fragment">[lang]_[elang]_entry @{ entity = <a class="code" href="parser__macros_8h.html#a48fd5c8dbc18cdf9daaa5810227f829">CHECK_BLANK_ENTRY</a>; } @[lang]_callback
  @{ <a class="code" href="parser__macros_8h.html#e9fb722b81bbd8bb0e1de37941fab172">saw</a>([elang]_LANG)} =&gt; { fcall [lang]_[elang]_line; };
</pre></div><p>
What this does is checks for a blank entry, and if it is, counts the line as a line of parent language code. If it is not, the macro will not do anything. The machine then transitions into the child language.<h3><a class="anchor" name="line_outry_action">
Outry Pattern Actions</a></h3>
<div class="fragment"><pre class="fragment">@{ <a class="code" href="parser__macros_8h.html#aa1ebe818ec1c763a776cc580551f3e6">p</a> = <a class="code" href="parser__macros_8h.html#366fc4d3a72013313c8b00233a5a7690">ts</a>; fret; };
</pre></div><p>
What this does is sets the current Ragel parser position to the beginning of the outry so the line is counted as a line of parent language code if no child code is on the same line. The machine then transitions into the parent language.<h2><a class="anchor" name="entity">
Entity Identifying Machine</a></h2>
This machine does not have to be written as a line-by-line parser. It only has to identify the positions of language entities, such as whitespace, comments, strings, etc. in sequence. As a result they can be written much faster and more easily with less thought than a line counter. Using a scanner is most efficient. The callback function will be called for each entity parsed.<p>
The @ls, @ code, @comment, @queue, and @commit actions are completely unnecessary.<h3><a class="anchor" name="entity_scanner">
Scanner Structure</a></h3>
<div class="fragment"><pre class="fragment">[lang]_entity := |*
  entity1 ${ entity = ENTITY1; } =&gt; [lang]_ecallback;
  entity2 ${ entity = ENTITY2; } =&gt; [lang]_ecallback;
  ...
  entityn ${ entity = ENTITYN; } =&gt; [lang]_ecallback;
*|;
</pre></div><h3><a class="anchor" name="entity_action">
Main Action Structure</a></h3>
<div class="fragment"><pre class="fragment">action [lang]_ecallback {
  callback([lang]_LANG, [lang]_entities[entity], <a class="code" href="parser__macros_8h.html#cc0eb0fbef1d4e1ccb5cf27961af93ad">cint</a>(<a class="code" href="parser__macros_8h.html#366fc4d3a72013313c8b00233a5a7690">ts</a>), <a class="code" href="parser__macros_8h.html#cc0eb0fbef1d4e1ccb5cf27961af93ad">cint</a>(<a class="code" href="parser__macros_8h.html#49aa6b4212d238e0be3312cf89738b98">te</a>),
           userdata);
}
</pre></div><h3><a class="anchor" name="entity_embedded">
Parsers for Embedded Languages</a></h3>
TODO:<h2><a class="anchor" name="tests">
Including Written Tests for Parsers</a></h2>
You should have two kinds of tests for parsers. One will be a header file that goes in the 'test/unit/parsers/' directory and the other will be an input source file that goes in the 'test/src_dir/' and an expected output file that goes in the 'test/expected_dir/' directory.<p>
The header file will need to be "#include"ed in 'test/unit/test_parsers.h'. Then add the "all_[lang]_tests()" function to the "all_parser_tests()" function.<p>
Recompile the tests for the changes to take effect.<p>
The other files added to the 'test/{src,expected}_dir/' directories will be automatically detected and run with the test suite. </div>
<hr size="1"><address style="text-align: right;"><small>Generated on Fri Aug 28 15:20:08 2009 for ohcount by&nbsp;
<a href="http://www.doxygen.org/index.html">
<img src="doxygen.png" alt="doxygen" align="middle" border="0"></a> 1.5.9 </small></address>
</body>
</html>