[ProgSoc] on regularity was: Context-affinitive parsing w/ context-free grammar

Anand Kumria wildfire at progsoc.uts.edu.au
Fri Sep 25 00:11:39 EST 2009


On Thu, Sep 24, 2009 at 8:08 AM, Roland Turner <raz at raz.cx> wrote:

> I suspect that the answer to your question is fortran.
>

Or jumanji. That is pretty much always a valid answer for most questions.


>
> Chomksy gives us three interesting groups of languages to think about:
>
> - regular,
> - context-free and
> - context-sensitive.
>
> Regular languages can be described using regular expressions and
> recognised using a finite-state automaton. This provides for blistering
> speed (think: one memory-access-cycle per byte of input), fixed response
> time and particularly compact description. Note that perl expressions
> aren't regular (in particular, they include back-reference) despite
> perl's use of the term.
>
>
Hmm, I was not aware that a regex syntax that included back references is
not a regular language. Is this because looking for the matches requires a
stack?

Actually, would it necessarily -- if you define a unit of input (e.g. a line
terminated with either CR, LF or some random combination of the two)  --
then you can perform the matching without a stack.

Somewhat confused.

Cheers,
Anand
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://progsoc.org/pipermail/progsoc/attachments/20090924/30921780/attachment.htm 


More information about the Progsoc mailing list