<p>if you don't count rembering the symbols of previous lines it's a regular language here's the regex as I see it (<code>&lt;char&gt;</code> is translated to <code>[a-z]</code>)</p>

<pre><code>[a-z]\s*,\s*([a-z]|None)\s*,\s*(R|L|P[a-z](R|L))\s*,\s*[a-z]\n
</code></pre>

<p>use capturing groups as necessary ;)</p>

CC BY-SA 3.0
2011-09-05T21:07:22.173Z
So then it's safe to say that the language is regular and the parser need only be a DSM? That's what I suspected, thanks.
Rein Henrichs
CC BY-SA 3.0
2011-09-06T06:26:17.503Z
@Rein the control of a TM is usually represented as a finite-state machine which characterize regular languages, so you shouldn't be surprised that the grammar you described is regular.
Artem Kaznatcheev
CC BY-SA 3.0
2011-09-06T08:12:58.643Z
@Artem Good point, although in Turing's later examples he groups instructions by configuration name, which I believe would require a context-free grammar as ratchet freak implied?
Rein Henrichs
CC BY-SA 3.0
2011-09-06T08:29:42.670Z
@rein what I meant with capturing groups is [this](http://perldoc.perl.org/perlre.html#Capture-groups) I just named it for if you wanted to use the regex parser built into a lot of languages
ratchet freak
CC BY-SA 3.0
2011-09-06T08:34:06.567Z
@ratchet I understand capturing groups. I was referring to your statement, "if you don't count rembering the symbols of previous lines it's a regular language". What if you *do* need to rememeber the symbols (idents) of previous lines, as Turing's later tables did?
Rein Henrichs
CC BY-SA 3.0
2011-09-06T08:40:01.870Z
@rein if the language of possible symbols is infinite; a context-sensitive grammar. but that's easier to describe as an extension of the regular language with constraints on some parts that will be checked separately (not through the normal parser automaton)
ratchet freak
CC BY-SA 3.0
2011-09-05T20:49:01.610Z
2011-09-05T20:49:01.610Z
ratchet freak
<p>In the process of writing a Turing machine simulator, I decided on a machine representation in ASCII that closely mirrors Turing's original machine tables. I am interested in the formal categorization of the grammar and the simplest type of parser required to implement it, and in a more formal description of same. The grammar is as follows:</p>

<pre><code>&lt;instruction&gt; ::= &lt;ident&gt; "," &lt;symbol&gt; "," &lt;operation&gt; "," &lt;ident&gt; &lt;EOL&gt;
      &lt;ident&gt; ::= &lt;char&gt;
      &lt;symbol ::= &lt;char&gt; | 'None'
  &lt;operation&gt; ::= &lt;movement&gt; | &lt;write&gt; &lt;movement&gt;
      &lt;write&gt; ::= 'P' &lt;char&gt; | 'E'
    &lt;movement ::= 'R' | 'L'
</code></pre>

<p>An example Turing machine table written in this grammar is as follows:</p>

<pre><code>b, None, P0R, c
c, None, R,   e
e, None, P1R, f
f, None, R,   b
</code></pre>

<p>It is clear to me that since this grammar is expressible in BNF, it must then be at most context-free, but is there a more accurate (more strict) categorization? The lack of left-recursion implies that it could be parsed with a recursive descent parser, but is there a simpler parser that would be capable of this grammar? How would one describe this grammar and its (simplest) associated parser?</p>

<fl.formal-languages><grammars><parsing><compilers><context-free-languages>
Describing a grammar and associated parser
Rein Henrichs
# Describing a grammar and associated parser

(Asked by: username_0 on 2011-09-05)

In the process of writing a Turing machine simulator, I decided on a machine representation in ASCII that closely mirrors Turing's original machine tables. I am interested in the formal categorization of the grammar and the simplest type of parser required to implement it, and in a more formal description of same. The grammar is as follows:
 ::=  ","  ","  ","  
       ::= 
       | 'None'
   ::=  |  
       ::= 'P'  | 'E'
    
An example Turing machine table written in this grammar is as follows:
b, None, P0R, c
c, None, R,   e
e, None, P1R, f
f, None, R,   b

It is clear to me that since this grammar is expressible in BNF, it must then be at most context-free, but is there a more accurate (more strict) categorization? The lack of left-recursion implies that it could be parsed with a recursive descent parser, but is there a simpler parser that would be capable of this grammar? How would one describe this grammar and its (simplest) associated parser?

**Tags:** fl.formal-languages, grammars, parsing, compilers, context-free-languages


---

## 1 answers

### Answer by username_1 on 2011-09-05. Score: 2 | Accepted answer

if you don't count rembering the symbols of previous lines it's a regular language here's the regex as I see it ( is translated to [a-z])
[a-z]\s*,\s*([a-z]|None)\s*,\s*(R|L|P[a-z](R|L))\s*,\s*[a-z]\n

use capturing groups as necessary ;)

> **Comments:**
> **username_0**: So then it's safe to say that the language is regular and the parser need only be a DSM? That's what I suspected, thanks.  
> **username_2**: @Rein the control of a TM is usually represented as a finite-state machine which characterize regular languages, so you shouldn't be surprised that the grammar you described is regular.  
> **username_0**: @Artem Good point, although in Turing's later examples he groups instructions by configuration name, which I believe would require a context-free grammar as username_1 implied?  
> **username_1**: @rein what I meant with capturing groups is [this](http://perldoc.perl.org/perlre.html#Capture-groups) I just named it for if you wanted to use the regex parser built into a lot of languages  
> **username_0**: @ratchet I understand capturing groups. I was referring to your statement, "if you don't count rembering the symbols of previous lines it's a regular language". What if you *do* need to rememeber the symbols (idents) of previous lines, as Turing's later tables did?  
> **username_1**: @rein if the language of possible symbols is infinite; a context-sensitive grammar. but that's easier to describe as an extension of the regular language with constraints on some parts that will be checked separately (not through the normal parser automaton)  

---

