On Wed, 5 Sep 2007 00:04:04 +0200, "Thomas" <·······@o2.pl> wrote:
>I just read the definition of LL parser, and have to write the lisp
>interpreter. Is LL(1) parser enought for lisp language ?
IIRC from Scheme, you need at least LL(2) to handle the optional parts
of forms like IF and LET et al. Whether that is sufficient I don't
know offhand.
As an open question to Matthias or whoever, I don't really see how
readtable handling would materially affect the parser's LL complexity.
Macro character parsing itself is LL(1) and it would be subsumed by
the greater complexity of parsing the forms. What is the extra
complexity?
George
--
for email reply remove "/" from address
George Neuner wrote:
> As an open question to Matthias or whoever, I don't really see how
> readtable handling would materially affect the parser's LL complexity.
> Macro character parsing itself is LL(1) and it would be subsumed by
> the greater complexity of parsing the forms. What is the extra
> complexity?
Can you construct (theoretically) an LL(n) grammar that can produce any
Common Lisp program?
Matthias Buelow <···@incubus.de> writes:
> George Neuner wrote:
>
> > As an open question to Matthias or whoever, I don't really see how
> > readtable handling would materially affect the parser's LL complexity.
> > Macro character parsing itself is LL(1) and it would be subsumed by
> > the greater complexity of parsing the forms. What is the extra
> > complexity?
>
> Can you construct (theoretically) an LL(n) grammar that can produce any
> Common Lisp program?
I'm pretty sure you trivially can, but probably because you aren't
asking the question you think you are asking.
Common Lisp is defined in terms of structure, not in terms of text.
So any strange syntax you have trouble with can almost surely be
compensated for by some other syntax that yields the same object.
The notion of a grammar generating programs involves a type/category
error.
Programs are objects, not syntaxes. The reader yields objects, not
programs. There is an extra level of indirection in there. As a
result, there are probably many syntaxes that lead to the same object
and generating all the possible objects that are programs does not
require generating all the possible textual syntaxes that would, if
read, yield objects that are valid programs.
(Importantly, too, there are valid programs that print the same but
mean different things because their object identity is different.)
Regardless, though, I'm curious: what is someone planning to _do_ with
this information? Why is the question being asked?
Kent M Pitman wrote:
> Programs are objects, not syntaxes. The reader yields objects, not
> programs. There is an extra level of indirection in there. As a
> result, there are probably many syntaxes that lead to the same object
> and generating all the possible objects that are programs does not
> require generating all the possible textual syntaxes that would, if
> read, yield objects that are valid programs.
Yes but the OP was asking whether the "Lisp language" can be parsed by
an LL parser, by which I understand that he means in textual source-code
form, otherwise it wouldn't make much sense.
In the case of Common Lisp, parsing Lisp source code with an LL(k)
parser is not possible, since read macro dispatches make parsing the
language Turing-complete, which cannot be decided by a parser that can
handle only (a subset of) context-free languages.
> Regardless, though, I'm curious: what is someone planning to _do_ with
> this information? Why is the question being asked?
I guess it's a parser generator exercise, since basic Lisp (without
extensible syntax) is relatively easy to write a grammar for.
Matthias Buelow <···@incubus.de> wrote:
+---------------
| Yes but the OP was asking whether the "Lisp language" can be parsed by
| an LL parser, by which I understand that he means in textual source-code
| form, otherwise it wouldn't make much sense.
+---------------
A better question might be whether the Common Lisp *reader* --
the CLHS function READ -- can usefully be implemented using an
LL parser. Having once written most of a CL READ in C, ISTR that
you need at least one and maybe in some rare cases two tokens
of read-ahead [when parsing dotted lists maybe?] to decide what
to do next using straightforward recursive descent [which is
sort of LL, right?]. It's not all that hard to do. [My reader
was less than 500 lines of C.]
But because of "#." and backquote & friends and other readmacros,
I doubt a *full* CL reader can be implemented using any kind of
"pure" or static table-driven parser, LL or otherwise, since you
need to be able to call back into Lisp at READ time.
-Rob
-----
Rob Warnock <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
On Thu, 06 Sep 2007 03:25:00 -0500, ····@rpw3.org (Rob Warnock) wrote:
>Matthias Buelow <···@incubus.de> wrote:
>+---------------
>| Yes but the OP was asking whether the "Lisp language" can be parsed by
>| an LL parser, by which I understand that he means in textual source-code
>| form, otherwise it wouldn't make much sense.
>+---------------
>
>A better question might be whether the Common Lisp *reader* --
>the CLHS function READ -- can usefully be implemented using an
>LL parser. Having once written most of a CL READ in C, ISTR that
>you need at least one and maybe in some rare cases two tokens
>of read-ahead [when parsing dotted lists maybe?] to decide what
>to do next using straightforward recursive descent [which is
>sort of LL, right?]. It's not all that hard to do. [My reader
>was less than 500 lines of C.]
>
>But because of "#." and backquote & friends and other readmacros,
>I doubt a *full* CL reader can be implemented using any kind of
>"pure" or static table-driven parser, LL or otherwise, since you
>need to be able to call back into Lisp at READ time.
Actually I think its only general readtable processing that is
troublesome. The set of standard abbreviation macros can be easily
recognized as special cases.
George
--
for email reply remove "/" from address
On Wed, 05 Sep 2007 12:37:48 +0200, Matthias Buelow <···@incubus.de>
wrote:
>George Neuner wrote:
>
>> As an open question to Matthias or whoever, I don't really see how
>> readtable handling would materially affect the parser's LL complexity.
>> Macro character parsing itself is LL(1) and it would be subsumed by
>> the greater complexity of parsing the forms. What is the extra
>> complexity?
>
>Can you construct (theoretically) an LL(n) grammar that can produce any
>Common Lisp program?
In general ... no.
Kent pointed out (and I guess you were alluding to) that readtable
macros might do absolutely anything - including parsing a completely
different language - and so it is very hard to reason about the
grammar complexity of a Lisp program.
If you confine the problem to Lisp syntax then the answer is yes.
From experience, I know Scheme grammar is mostly LL(1) with just a
couple of forms that require more look ahead - LL(2) or LL(3), nothing
drastically hard. A grammar for Lisp should be of the same order
complexity - Lisp's additional keywords, expanded parameter lists, and
multiple name spaces don't materially affect the grammar complexity
... the parser complexity, but not the grammar.
George
--
for email reply remove "/" from address
George Neuner <·········@comcast.net> writes:
> On Wed, 05 Sep 2007 12:37:48 +0200, Matthias Buelow <···@incubus.de>
> wrote:
>
> >Can you construct (theoretically) an LL(n) grammar that can produce any
> >Common Lisp program?
>
> In general ... no.
>
> Kent pointed out (and I guess you were alluding to) that readtable
> macros might do absolutely anything - including parsing a completely
> different language - and so it is very hard to reason about the
> grammar complexity of a Lisp program.
>
> If you confine the problem to Lisp syntax then the answer is yes.
Terminology: You mean to say "pre-defined Lisp syntax". The stuff written
by users is _still_ Lisp syntax.
I'm afraid I feel it necessary to belabor this point because it's key:
We certainly don't refer to programs that are not given by the standard but
written by users as if they were not "Lisp programs". The same should be
true of Lisp syntax.
By design, Common Lisp intends you to extend the syntax. This is not
a baroque exception that may be swept under the rug as an anomalous
and embarrassing quirk. It is absolutely core to the way that you are
intended to program, and it is a key missing feature that drives me
absolutely nuts when working with other languages. If I had this
ability to extend and control the language syntax in other languages,
I would consider that a MAJOR step forward in those languages bridging
the gaping void between Lisp and those languages. The ability to merely
tweak parse precedences, touted by a recent vocal super-minority as an
important capability, pales in comparison to this very valuable feature.
I have written programs that represent complex technologies (like XML,
MIF, and other document structures, Symbolic Algebra expressions, new
languagey datatypes as specific as URLs or as general as alternate
object systems, and so on) as things with print and read syntaxes that
allowed me to use this kind of data compactly and gracefully as
program data, including as literal constants in the middle of other
code. There is just no comparison between that level of
organizational/presentational capability and mere changing of the
order of operators or removing a few parens.
My expectations for mainstream languages are so low that I find myself
cheering when languages like C# even have ubiquitous .ToString() on all
Objects. That, at least, means there's a vague way to debug stuff.
However, it's nothing compared to Lisp not just because it's only half
a protocol (there's no way to use the text that comes from there as input,
and consequently the format of .ToString() results varies hugely in a way
that makes them not comparable to the output of PRIN1. It's more like
what PRINC does, which would never be a suitable counterpart to READ).
Common Lisp, in particular, builds on many years of development by other
dialects, by offering powerful tools for users to gracefully extend the
reader and printer in a way that makes complicated, interconnected programs
be able to interchange programs and data not just as objects but even
when marshaled as strings that must be read (i.e. parsed).
> From experience, I know Scheme grammar is mostly LL(1) with just a
> couple of forms that require more look ahead - LL(2) or LL(3), nothing
> drastically hard. A grammar for Lisp should be of the same order
> complexity - Lisp's additional keywords, expanded parameter lists, and
> multiple name spaces don't materially affect the grammar complexity
> ... the parser complexity, but not the grammar.
Yes, if I recall how it went in the design discussions, the authors of
the Scheme report went to considerable explicit work to design the
Scheme language in an appropriately restrictive way (given that
conservativism is one of its core themes) that was explicitly intended
to allow people who wanted a "parser model" to just do that without
realizing that others were using an object model for semantics. Both
styles were intended to work.
(This, incidentally, places some pressure on the language when it
comes to issues like gensyms [which have little meaning as parsed
entities since by definition they are objects intended to have no
parsed representation so you can't accidentally make one], and I don't
recall how that was resolved. I watched the discussions go by but
didn't involve myself heavily in that aspect of the language, other
than to fuss a bit about the problems that result with trying to make
'gensym' work in a parsed situation. Probably this ended up finessed
by the hygienic-macro system, but I don't have the time to dig--maybe
someone else can look this up and report back here on it if they
care.)
On 06 Sep 2007 08:50:12 -0400, Kent M Pitman <······@nhplace.com>
wrote:
>George Neuner <·········@comcast.net> writes:
>
>> On Wed, 05 Sep 2007 12:37:48 +0200, Matthias Buelow <···@incubus.de>
>> wrote:
>>
>> >Can you construct (theoretically) an LL(n) grammar that can produce any
>> >Common Lisp program?
>>
>> In general ... no.
>>
>> Kent pointed out (and I guess you were alluding to) that readtable
>> macros might do absolutely anything - including parsing a completely
>> different language - and so it is very hard to reason about the
>> grammar complexity of a Lisp program.
>>
>> If you confine the problem to Lisp syntax then the answer is yes.
>
>Terminology: You mean to say "pre-defined Lisp syntax". The stuff written
>by users is _still_ Lisp syntax.
Sort of. What I mean exactly is any sexpr syntax that conforms to
Lisp's prefix notation. Whether the symbols are pre-defined or user
defined is not really relevant to parsing them. Lispy macros also
fall into this category - even LOOP is very simple to parse in LL
despite not following normal Lisp conventions.
I think part of the issue in this discussion is where the boundary is
drawn between parsing and analyzing/evaluating the resultant internal
form. The Lisp reader conflates these operations (as do parsers in
compilers for most languages) for efficiency, but it is always
technically possible to separate them and talk about just the "parser"
or the "evaluator". I've been talking mostly about just parsing
because that's how this thread began, but I understand your point.
>I'm afraid I feel it necessary to belabor this point because it's key:
>
>We certainly don't refer to programs that are not given by the standard but
>written by users as if they were not "Lisp programs". The same should be
>true of Lisp syntax.
>
>By design, Common Lisp intends you to extend the syntax. This is not
>a baroque exception that may be swept under the rug as an anomalous
>and embarrassing quirk. It is absolutely core to the way that you are
>intended to program, and it is a key missing feature that drives me
>absolutely nuts when working with other languages. If I had this
>ability to extend and control the language syntax in other languages,
>I would consider that a MAJOR step forward in those languages bridging
>the gaping void between Lisp and those languages. The ability to merely
>tweak parse precedences, touted by a recent vocal super-minority as an
>important capability, pales in comparison to this very valuable feature.
>
>I have written programs that represent complex technologies (like XML,
>MIF, and other document structures, Symbolic Algebra expressions, new
>languagey datatypes as specific as URLs or as general as alternate
>object systems, and so on) as things with print and read syntaxes that
>allowed me to use this kind of data compactly and gracefully as
>program data, including as literal constants in the middle of other
>code. There is just no comparison between that level of
>organizational/presentational capability and mere changing of the
>order of operators or removing a few parens.
>
>My expectations for mainstream languages are so low that I find myself
>cheering when languages like C# even have ubiquitous .ToString() on all
>Objects. That, at least, means there's a vague way to debug stuff.
>However, it's nothing compared to Lisp not just because it's only half
>a protocol (there's no way to use the text that comes from there as input,
>and consequently the format of .ToString() results varies hugely in a way
>that makes them not comparable to the output of PRIN1. It's more like
>what PRINC does, which would never be a suitable counterpart to READ).
>
>Common Lisp, in particular, builds on many years of development by other
>dialects, by offering powerful tools for users to gracefully extend the
>reader and printer in a way that makes complicated, interconnected programs
>be able to interchange programs and data not just as objects but even
>when marshaled as strings that must be read (i.e. parsed).
>
>> From experience, I know Scheme grammar is mostly LL(1) with just a
>> couple of forms that require more look ahead - LL(2) or LL(3), nothing
>> drastically hard. A grammar for Lisp should be of the same order
>> complexity - Lisp's additional keywords, expanded parameter lists, and
>> multiple name spaces don't materially affect the grammar complexity
>> ... the parser complexity, but not the grammar.
>
>Yes, if I recall how it went in the design discussions, the authors of
>the Scheme report went to considerable explicit work to design the
>Scheme language in an appropriately restrictive way (given that
>conservativism is one of its core themes) that was explicitly intended
>to allow people who wanted a "parser model" to just do that without
>realizing that others were using an object model for semantics. Both
>styles were intended to work.
>
>(This, incidentally, places some pressure on the language when it
>comes to issues like gensyms [which have little meaning as parsed
>entities since by definition they are objects intended to have no
>parsed representation so you can't accidentally make one], and I don't
>recall how that was resolved. I watched the discussions go by but
>didn't involve myself heavily in that aspect of the language, other
>than to fuss a bit about the problems that result with trying to make
>'gensym' work in a parsed situation. Probably this ended up finessed
>by the hygienic-macro system, but I don't have the time to dig--maybe
>someone else can look this up and report back here on it if they
>care.)
George
--
for email reply remove "/" from address
George Neuner <·········@comcast.net> wrote:
+---------------
| Kent M Pitman <······@nhplace.com> wrote:
| >George Neuner <·········@comcast.net> writes:
| >> If you confine the problem to Lisp syntax then the answer is yes.
| >
| >Terminology: You mean to say "pre-defined Lisp syntax". The stuff written
| >by users is _still_ Lisp syntax.
|
| Sort of. What I mean exactly is any sexpr syntax that conforms to
| Lisp's prefix notation.
+---------------
I think you've missed Kent's point entirely. When coding a CL READ in C
[and ignoring READ's &OPTIONAL parameters for the nonce], the top level
"parsing" routine looks like this [or something closely equivalent]:
lispobj
reader(lispobj stream)
{
for (;;) { /* Needed for reader macros that do nothing. */
lispobj obj;
int c = flush_whitespace(stream);
if (EOF == c)
return type_EOF;
obj = (*read_macro_table[c])(stream, c);
if (obj != type_ZeroValues) /* Comments, #+/-, and the like. */
return obj;
/* else keep reading... */
}
}
The key is that *ALL* "parsing" starts with that crucial indirection
through the current readtable. There *is* no such thing as a
"[conforming] s-expr syntax" unless the readmacro currently in
force for #\( just happens to be one which gives you the "usual"
s-expr syntax.
-Rob
p.s. And, no, that's not the way you'd really do it [except for an
inflexible toy CL subset], since that makes it too hard to switch
readtables. You need to add a level of indirection:
...
obj = (*(*read_macro_table)[c])(stream, c);
...
-----
Rob Warnock <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
George Neuner <·········@comcast.net> writes:
> >Terminology: You mean to say "pre-defined Lisp syntax". The stuff written
> >by users is _still_ Lisp syntax.
>
> Sort of. What I mean exactly is any sexpr syntax that conforms to
> Lisp's prefix notation.
Well, except that this may be useful for some special-purpose one-off
thing, since virtually anything may be useful to a thing, but in terms
of "describing CL", it's not meaningful to say "handles things people
might write who have no pre-defined agreement with you" other than to
say "the full set of things people might write".
I asked earlier, I think, or maybe I started to ask and then didn't
send it, so I'll ask again: what would one do differently if one had a
parser for this allegedly interesting subset? Is there a goal here
that is logically distinct from discussing what the set of numeric
values Lisp could compute if bignums were not there? The reader does
define readmacros so I don't see quite what people are getting at in
discussing the properties of the reader absent readmacros. Is this
just a discussion of making toys that will grow up to not be able to
use the tools that bootstrapped them? Is there a proposal in play for
extending the LL(n) concept to be usefully able to accept arbitrary
code in the middle [as, for example, a "pratt parser" might do?] I'm
just completely out of context as to the goal, so it keeps catching my
eye that other readers who might be following along might be done the
misservice of thinking this was a discussion of the properties of the
actual CL reader, and it's not as far as I can see.
I guess you _could_ be talking about some hypothetical readmacro-free
subset, but you haven't appeared to label the conversation taht way. I
have to say that the reason I chimed in is that it appeared that some
people involved in the discussion (I am not sure I even know whom, and
I'm not trying to point fingers, but generally) didn't seem realize
readmacros are there, that they are important to day-to-day use of
many programmers, and call for a different way of thinking than
standard parsers tend to promote. It's like having a discussion of
DEFSTRUCT not realizing CLOS is there and talking about whether
Common Lisp would benefit from multiple inheritance. Anyone looking
on would take a discussion as if it was saying "CL doesn't have that
already."
I've got nothing against hypothetical discussions, when properly
labeled, but just starting a discussion that uses either a
hypothetical or a gaping whole in caveat-declaration is not that
because it risks that people reading on will get confused. My only
goal in injecting myself here is to make sure that people don't
mistake all the discussion here for discussion of what the real,
non-hypothetical Lisp reader actually does and needs. As soon as I
see appropriate caveats being mentioned in places that will avoid
confusion, I'll recede back into the background.
The only implicit constraint CL places on things, and I doubt it's
formally spelled out, is that the syntax you pick should, if it really
wants to sit inside other expressions [and it isn't required to do that
since you migth want to make your own readtable with data to be parsed
by READ that isn't intended to be embedded in s-expressions], is that
it wants to cleanly start and stop so that it can be embedded. So if you
make a syntax: #[...] then it's assumed that you can also make
(... #[...]). So if you make a FORTRAN parser and it parses to end of
file, you can't use eof as a terminator and still be embedded in other
expressions. But other than that, it pretty much can terminate as it likes.
Lisp-savvy text editors like Emacs (not talking about emacs-lisp here,
but just the implicit constraints of using something that even thinks
it understands Lisp) happens to usually place additional constraints,
like that the notation should not locally confuse the syntax
categorizations it makes, which is why #\x is chosen as it is, so that
if Emacs doesn't know what #\ is, it will presumably still know that \
quotes the character after it, which will mean #\a is harmless but,
importantly, #\( will not be taken as a syntactic open-paren. So if
you extend things in a way as to make a readmacro that returns an
n-length string by doing ··@abc, for example, you are going to
probably make Emacs mad because while abc is fine ··@((| is going to
trick Emacs into thinking there are pending open parens followed by a
pending |, all three of which characters need matches (and in the right
order).
But beyond all of that, there is still a huge wealth of difference in
what these readmacros might do, and certainly describing those things
in a grammar is not really useful because the grammar will have a gaping
"or anything else" at the bottom.
> Whether the symbols are pre-defined or user
> defined is not really relevant to parsing them. Lispy macros also
> fall into this category - even LOOP is very simple to parse in LL
> despite not following normal Lisp conventions.
I'm not talking about [expression] macros, I'm talking about reader macros.
Which are you talking about, because LOOP is something that takes an
expression as its argument, that is this single pointer (noted as argptr
here) is the argument to LOOP:
argptr
|
v
+---+---+ +---+---+ +---+---+ +---+---+ +---+---+
| . | .---->| . | .---->| . | .---->| . | .---->| . | .----> ...
+-|-+---+ +-|-+---+ +-|-+---+ +-|-+---+ +-|-+---+
v v | v v
LOOP FOR | IN +---+---+ +---+---+
+---+---+ | . | .---->| . | / |
| . | . | +-|-+---+ |-|-+---+
+-|-+-|-+ v v
v v FIRST Y
A B
I don't know any parsers that take pointers to complex object structures as
args, but I suppose there could be such. Ordinarily, I assume that parsers
take either a string
"LOOP FOR (A . B) IN (FIRST Y) ..."
or a token stream
#("LOOP" "FOR" "(" "A" "." "B" ")" "IN" "(" "FIRST" "Y" ")" ...)
but Lisp uses neither of these.
> I think part of the issue in this discussion is where the boundary is
> drawn between parsing and analyzing/evaluating the resultant internal
> form. The Lisp reader conflates these operations (as do parsers in
> compilers for most languages) for efficiency, but it is always
> technically possible to separate them and talk about just the "parser"
> or the "evaluator".
As I see it, Lisp does not conflate them. It is one of the few
languages that keeps the separation extraordinarily clear.
READ returns objects. EVAL is defined on objects.
For convenience of reference, we refer by syntax to the objects that EVAL
takes as inputs since the nature of those objects are self-evident through
their notation thanks to the clear definition of READ. That's almost
unheard of in other languages.
> I've been talking mostly about just parsing
> because that's how this thread began, but I understand your point.
In the messages I've read and replied to, it doesn't seem clear.
Perhaps you're assuming people read whole threads from start to end
and recall their state, but that's asking a lot of usenet readers.
I think we're talking at crossed purposes and we should probably stop
before it goes any further. I do appreciate your exposition on the
workings of the Lisp reader - as I stated earlier, my experience with
Lisp-like languages has been mainly with Scheme which doesn't have a
standard for reader extension - in Scheme reader extension, if
supported at all, is implementation dependent.
One thing I would like to say though before we stop: the original
poster asked a theoretical question ... whether Lisp (he did not
specify CL) was LL(1). The answer to that is "no" regardless of
whether readtable processing is considered - some of the basic (I want
to avoid the word "standard") language forms are not LL(1).
However, because the reader can invoke any behavior whatsoever via the
readtable it can be made to accept virtually any language. Given
that, it makes little sense to talk about the grammatical complexity
of Common Lisp or the complexity of the reader because one can't even
define a grammar for the accepted language other than in situ.
Perhaps this is what you (Kent) and Matthias and Rob were getting at
all along. But then it doesn't make sense either to talk about Common
Lisp as a distinct language because it can be any language.
Also, I was not discussing CL in particular but rather sexpr based
languages which resemble Lisp in notation. I understand that that was
not made clear, and for that, I apologize.
On 06 Sep 2007 21:34:01 -0400, Kent M Pitman <······@nhplace.com>
wrote:
>George Neuner <·········@comcast.net> writes:
>
>> >Terminology: You mean to say "pre-defined Lisp syntax". The stuff written
>> >by users is _still_ Lisp syntax.
>>
>> Sort of. What I mean exactly is any sexpr syntax that conforms to
>> Lisp's prefix notation.
>
>Well, except that this may be useful for some special-purpose one-off
>thing, since virtually anything may be useful to a thing, but in terms
>of "describing CL", it's not meaningful to say "handles things people
>might write who have no pre-defined agreement with you" other than to
>say "the full set of things people might write".
>
>I asked earlier, I think, or maybe I started to ask and then didn't
>send it, so I'll ask again: what would one do differently if one had a
>parser for this allegedly interesting subset? Is there a goal here
>that is logically distinct from discussing what the set of numeric
>values Lisp could compute if bignums were not there? The reader does
>define readmacros so I don't see quite what people are getting at in
>discussing the properties of the reader absent readmacros. Is this
>just a discussion of making toys that will grow up to not be able to
>use the tools that bootstrapped them? Is there a proposal in play for
>extending the LL(n) concept to be usefully able to accept arbitrary
>code in the middle [as, for example, a "pratt parser" might do?] I'm
>just completely out of context as to the goal, so it keeps catching my
>eye that other readers who might be following along might be done the
>misservice of thinking this was a discussion of the properties of the
>actual CL reader, and it's not as far as I can see.
>
>I guess you _could_ be talking about some hypothetical readmacro-free
>subset, but you haven't appeared to label the conversation taht way. I
>have to say that the reason I chimed in is that it appeared that some
>people involved in the discussion (I am not sure I even know whom, and
>I'm not trying to point fingers, but generally) didn't seem realize
>readmacros are there, that they are important to day-to-day use of
>many programmers, and call for a different way of thinking than
>standard parsers tend to promote. It's like having a discussion of
>DEFSTRUCT not realizing CLOS is there and talking about whether
>Common Lisp would benefit from multiple inheritance. Anyone looking
>on would take a discussion as if it was saying "CL doesn't have that
>already."
>
>I've got nothing against hypothetical discussions, when properly
>labeled, but just starting a discussion that uses either a
>hypothetical or a gaping whole in caveat-declaration is not that
>because it risks that people reading on will get confused. My only
>goal in injecting myself here is to make sure that people don't
>mistake all the discussion here for discussion of what the real,
>non-hypothetical Lisp reader actually does and needs. As soon as I
>see appropriate caveats being mentioned in places that will avoid
>confusion, I'll recede back into the background.
>
>The only implicit constraint CL places on things, and I doubt it's
>formally spelled out, is that the syntax you pick should, if it really
>wants to sit inside other expressions [and it isn't required to do that
>since you migth want to make your own readtable with data to be parsed
>by READ that isn't intended to be embedded in s-expressions], is that
>it wants to cleanly start and stop so that it can be embedded. So if you
>make a syntax: #[...] then it's assumed that you can also make
>(... #[...]). So if you make a FORTRAN parser and it parses to end of
>file, you can't use eof as a terminator and still be embedded in other
>expressions. But other than that, it pretty much can terminate as it likes.
>
>Lisp-savvy text editors like Emacs (not talking about emacs-lisp here,
>but just the implicit constraints of using something that even thinks
>it understands Lisp) happens to usually place additional constraints,
>like that the notation should not locally confuse the syntax
>categorizations it makes, which is why #\x is chosen as it is, so that
>if Emacs doesn't know what #\ is, it will presumably still know that \
>quotes the character after it, which will mean #\a is harmless but,
>importantly, #\( will not be taken as a syntactic open-paren. So if
>you extend things in a way as to make a readmacro that returns an
>n-length string by doing ··@abc, for example, you are going to
>probably make Emacs mad because while abc is fine ··@((| is going to
>trick Emacs into thinking there are pending open parens followed by a
>pending |, all three of which characters need matches (and in the right
>order).
>
>But beyond all of that, there is still a huge wealth of difference in
>what these readmacros might do, and certainly describing those things
>in a grammar is not really useful because the grammar will have a gaping
>"or anything else" at the bottom.
>
>> Whether the symbols are pre-defined or user
>> defined is not really relevant to parsing them. Lispy macros also
>> fall into this category - even LOOP is very simple to parse in LL
>> despite not following normal Lisp conventions.
>
>I'm not talking about [expression] macros, I'm talking about reader macros.
>Which are you talking about, because LOOP is something that takes an
>expression as its argument, that is this single pointer (noted as argptr
>here) is the argument to LOOP:
>
> argptr
> |
> v
> +---+---+ +---+---+ +---+---+ +---+---+ +---+---+
> | . | .---->| . | .---->| . | .---->| . | .---->| . | .----> ...
> +-|-+---+ +-|-+---+ +-|-+---+ +-|-+---+ +-|-+---+
> v v | v v
> LOOP FOR | IN +---+---+ +---+---+
> +---+---+ | . | .---->| . | / |
> | . | . | +-|-+---+ |-|-+---+
> +-|-+-|-+ v v
> v v FIRST Y
> A B
>
>I don't know any parsers that take pointers to complex object structures as
>args, but I suppose there could be such. Ordinarily, I assume that parsers
>take either a string
>
> "LOOP FOR (A . B) IN (FIRST Y) ..."
>
>or a token stream
>
> #("LOOP" "FOR" "(" "A" "." "B" ")" "IN" "(" "FIRST" "Y" ")" ...)
>
>but Lisp uses neither of these.
>
>
>> I think part of the issue in this discussion is where the boundary is
>> drawn between parsing and analyzing/evaluating the resultant internal
>> form. The Lisp reader conflates these operations (as do parsers in
>> compilers for most languages) for efficiency, but it is always
>> technically possible to separate them and talk about just the "parser"
>> or the "evaluator".
>
>As I see it, Lisp does not conflate them. It is one of the few
>languages that keeps the separation extraordinarily clear.
>
>READ returns objects. EVAL is defined on objects.
>
>For convenience of reference, we refer by syntax to the objects that EVAL
>takes as inputs since the nature of those objects are self-evident through
>their notation thanks to the clear definition of READ. That's almost
>unheard of in other languages.
>
>> I've been talking mostly about just parsing
>> because that's how this thread began, but I understand your point.
>
>In the messages I've read and replied to, it doesn't seem clear.
>Perhaps you're assuming people read whole threads from start to end
>and recall their state, but that's asking a lot of usenet readers.
That's a good point. It is sometimes hard to include enough context
for a message to stand alone. I apologize for my role in contributing
to the confusion.
George
--
for email reply remove "/" from address
George Neuner <·········@comcast.net> wrote:
+---------------
| I think we're talking at crossed purposes and we should probably stop...
...
| One thing I would like to say though before we stop: the original
| poster asked a theoretical question ... whether Lisp (he did not
| specify CL) was LL(1). The answer to that is "no" regardless of
| whether readtable processing is considered - some of the basic (I want
| to avoid the word "standard") language forms are not LL(1).
...
| Also, I was not discussing CL in particular but rather sexpr based
| languages which resemble Lisp in notation.
+---------------
As you note, it is possible even in non-CL sexpr-based languages
that some of the basic forms might not be LL(1). E.g., consider a
hypothetical dialect of Scheme which adopted John Foderaro's IF*[1]:
(if* <predicate> ; [I don't know where the THENRET fits in.]
then <form>...
elseif <form>...
elseif <form>...
else <form>...)
I don't think this is LL(1), yet a simple recursive-descent parser
can handle it easily.
On the other hand, is there anything in Standard Scheme
[either IEEE or R4RS, take your pick (I'm not sure about
whether R5RS macros break this or not)] that isn't LL(1)?
Or at least LL(n) for *small* "n"?
-Rob
[1] http://www.franz.com/~jkf/ifstar.txt
-----
Rob Warnock <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
From: Kent M Pitman
Subject: grammatical complexity [was: Re: simple lisp interpreter]
Date:
Message-ID: <uk5qyv4eg.fsf_-_@nhplace.com>
George Neuner <·········@comcast.net> writes:
> I think we're talking at crossed purposes and we should probably stop
> before it goes any further.
Well, that wasn't my intent either. Especially since you raise other
interesting questions here.
> However, because the reader can invoke any behavior whatsoever via the
> readtable it can be made to accept virtually any language. Given
> that, it makes little sense to talk about the grammatical complexity
> of Common Lisp or the complexity of the reader because one can't even
> define a grammar for the accepted language other than in situ.
Actually, I wish there were some notation of "grammatical complexity" that
was different than mere syntax-tokenization and grouping, which I might call
"syntactic complexity". In a sense, one might say CL has three levels, not
two:
text -> syntax -> structure -> grammar -> meaning
where other languages have just
text -> syntax/grammar -> meaning
I don't know of a particular literature on grammatical complexity, other
than perhaps the vaguely similar but perhaps analogous distinctions like
propositional/predicate logics.
Since you raise the point, is there anyone listening who knows
terminology for this that I might usefully apply in my own thoughts on
this? It might be related to the notion of expressional power I
sometimes throw around (and have informal ideas about how to express
that I've never written down) as an alternative to Turing power (which
is such a flat space that all things are equivalent and hence useless
to talk about as different); I think programs differ expressionally so
I posit some possible definition that would explain why.
That would be a more fun discussion for me. But I didn't mean to conflate
it with your discussion here, I just meant to say that Lisp tends to lean
heavy on grammatical issues and to eschew the syntactic.
Note further that I might mean to include macros in a discussion of
grammatical complexity, or I might just mean primitive language
syntax. I'm neutral on that. In a sense, macros give you the ability
to lift yourself to what seems like a more powerful space. But if you
can't describe the power as other than "Turing powerful" then you're,
by definition, not changing the power and you have to (bogusly) assume
you've done yourself no favor by moving from assembly language to
BASIC to Lisp to whatever; you're obliged to conclude that all of
these are equally good and to wonder why anyone spends time in
anything other than assembly language... So macros are probably not
the enabling factor of the power I refer to, but they are one way (of
possibly several) to enable experiments about the importance of that
power since they can shift the set of available
operators/forms/constructs and allow one to see whether programs
become easier/harder to write in the world augmented by their
presence. (Functional abstraction, object orientation, etc. are
perhaps others in the space. My question goes to the measuring of
power, not to the specific ways the capability manifests.)
I hope I'm making my question clear, but somehow I fear I'm not.
Maybe I've said it well enough that someone can clean it up and re-ask
it. :) But it seems to be the question that vexxes marketeers--i.e.,
how do I explain to someone why buying x or y paradigm adds "power"
other than just "telling success stories"...?
> Perhaps this is what you (Kent) and Matthias and Rob were getting at
> all along. But then it doesn't make sense either to talk about Common
> Lisp as a distinct language because it can be any language.
>
> Also, I was not discussing CL in particular but rather sexpr based
> languages which resemble Lisp in notation. I understand that that was
> not made clear, and for that, I apologize.
No harm done, and no apology needed from my point of view, but I do
appreciate the clarification of intent just to put the discussion into
context.
Kent M Pitman <······@nhplace.com> writes:
> Since you raise the point, is there anyone listening who knows
> terminology for this that I might usefully apply in my own thoughts on
> this?
What you call "meaning" is typically called "semantics" in the
literature. For syntax, one should distinguish between concrete syntax
and abstract syntax. The concrete syntax also contains whitespace,
newlines etc. that are of no relevance in the abstract syntax.
> Note further that I might mean to include macros in a discussion of
> grammatical complexity, or I might just mean primitive language
A misunderstanding I sometimes see in this group is that the concrete
syntax must necessarily closely correspond to the abstract syntax in
order for macros to be useful; but that's not the case: The concrete
syntax is completely peripheral in this regard, and many languages
provide, for example, both infix and prefix concrete syntax, yet a
completely uniform abstract syntax that macros can easily work on.
On Sep 10, 8:20 pm, Markus Triska <········@stud4.tuwien.ac.at> wrote:
> A misunderstanding I sometimes see in this group is that the concrete
> syntax must necessarily closely correspond to the abstract syntax in
> order for macros to be useful; but that's not the case: The concrete
> syntax is completely peripheral in this regard, and many languages
> provide, for example, both infix and prefix concrete syntax, yet a
> completely uniform abstract syntax that macros can easily work on.
What are the downsides (if any) to this approach?
Is all you need to do is define CONCRETE->ABSTRACT and its inverse?
Thanks,
Tayssir
From: Markus Triska
Subject: Re: grammatical complexity
Date:
Message-ID: <m1sl5lxdzv.fsf@gmx.at>
Tayssir John Gabbour <············@googlemail.com> writes:
> What are the downsides (if any) to this approach?
> Is all you need to do is define CONCRETE->ABSTRACT and its inverse?
As a *user*, you don't have to do anything, as you typically only see
a representation of the abstract syntax in macros. Functions like
"read" perform the concrete->abstract transformation for you. The
inverse (abstract->concrete) is part of what a "pretty-printer" does
and is typically not well-defined (there are several valid outputs).
As an *implementer*, you have to extend your parser to handle the
variants of the concrete syntax; that's hardly news: Concrete and
abstract syntax differ in Lisp as well (otherwise you'd have to handle
comments and the like in macros), and there are many concrete variants
(more newlines etc.) for one and the same abstract syntax tree.
On 10 Sep 2007 13:03:51 -0400, Kent M Pitman <······@nhplace.com>
wrote:
>George Neuner <·········@comcast.net> writes:
>
>> I think we're talking at crossed purposes and we should probably stop
>> before it goes any further.
>
>Well, that wasn't my intent either. Especially since you raise other
>interesting questions here.
>
>> However, because the reader can invoke any behavior whatsoever via the
>> readtable it can be made to accept virtually any language. Given
>> that, it makes little sense to talk about the grammatical complexity
>> of Common Lisp or the complexity of the reader because one can't even
>> define a grammar for the accepted language other than in situ.
>
>Actually, I wish there were some notation of "grammatical complexity" that
>was different than mere syntax-tokenization and grouping, which I might call
>"syntactic complexity".
I'm not sure there is much literature on this topic pertaining to
programming ... syntactic complexity is studied much more for natural
languages than for synthetic ones. Most literature on the complexity
of programming languages relates them to elements of the Chomsky
hierarchy.
>In a sense, one might say CL has three levels, not two:
>
> text -> syntax -> structure -> grammar -> meaning
>
>where other languages have just
>
> text -> syntax/grammar -> meaning
>
>I don't know of a particular literature on grammatical complexity, other
>than perhaps the vaguely similar but perhaps analogous distinctions like
>propositional/predicate logics.
All "interesting" languages - ie. those that have meaning - require
some kind of organizing structure.
I would order it differently (without including grammar) as
text -> syntax -> structure -> meaning
I don't include grammar because it is too generic a term and because
it covers syntax (more on that below).
>Since you raise the point, is there anyone listening who knows
>terminology for this that I might usefully apply in my own thoughts on
>this?
Is Chris F. Clark in the house? I know he lurks here.
>It might be related to the notion of expressional power I
>sometimes throw around (and have informal ideas about how to express
>that I've never written down) as an alternative to Turing power (which
>is such a flat space that all things are equivalent and hence useless
>to talk about as different); I think programs differ expressionally so
>I posit some possible definition that would explain why.
>
>That would be a more fun discussion for me. But I didn't mean to conflate
>it with your discussion here, I just meant to say that Lisp tends to lean
>heavy on grammatical issues and to eschew the syntactic.
I'm not sure I understand fully how you are using the terms. I'm
going to expound a little bit on how I view Lisp in linguistic terms.
Feel free to jump on my head (you will anyway 8-).
First, "syntax" has dual meaning - in linguistics it can refer to both
of a pattern and an instance of a pattern. It is proper to speak of
"a syntax" which denotes a particular pattern form which is a subset
of a grammar. Conversely a grammar can contain multiple syntax
patterns. Additionally, "syntax" is both singular and plural - it can
refer to one form or many and I will use it, in context, either way.
With Lisp the discussion is complicated by the issue of semantics.
Language semantics are, necessarily, defined on syntax[*] because
syntax denotes structure and structure denotes meaning. The question
then is, what exactly is the syntax of Lisp?
[*] There are, of course, additional semantics not defined by syntax
but we can ignore them for the moment.
Unlike virtually all other languages, Lisp defines a particular
(initial) intermediate representation for code composed of structured
graphs of Lisp objects, and further Lisp defines mappings from text to
objects and from a stylized form of source text, s-exprs, to graphs of
objects. However, not all text maps to legal code or data forms ...
Lisp's semantics are defined on only a particular set of objects and
graphs. Thus, I would say that the actual syntax of Lisp is that
particular set of structured object graphs for which semantics have
been defined. The grammar however, is the set of all possible
s-exprs, including those that don't map to legal code forms, _plus_
the set of all constructible Lisp objects which may or may not have a
human readable s-expr representation.
We've been going back and forth recently about how the readtable
changes things, but I really don't think it does. The result of
reading must be a graph of Lisp objects, but every possible Lisp
object is already recognized as being part of the grammar, therefore
there is no impact on grammar. Similarly, there is no effect on
syntax - either the external form is being compiled to Lisp, in which
case the result must be a legal code or data form governed by Lisp's
semantics, or the external form is being transformed in some way
outside of Lisp semantics in which case the result is undefined with
respect to Lisp.
>Note further that I might mean to include macros in a discussion of
>grammatical complexity, or I might just mean primitive language
>syntax. I'm neutral on that. In a sense, macros give you the ability
>to lift yourself to what seems like a more powerful space. But if you
>can't describe the power as other than "Turing powerful" then you're,
>by definition, not changing the power and you have to (bogusly) assume
>you've done yourself no favor by moving from assembly language to
>BASIC to Lisp to whatever; you're obliged to conclude that all of
>these are equally good and to wonder why anyone spends time in
>anything other than assembly language... So macros are probably not
>the enabling factor of the power I refer to, but they are one way (of
>possibly several) to enable experiments about the importance of that
>power since they can shift the set of available
>operators/forms/constructs and allow one to see whether programs
>become easier/harder to write in the world augmented by their
>presence. (Functional abstraction, object orientation, etc. are
>perhaps others in the space. My question goes to the measuring of
>power, not to the specific ways the capability manifests.)
>
>I hope I'm making my question clear, but somehow I fear I'm not.
I guess it depends on how you define "power". I'm not aware of any
objective scale relating languages in terms of power ... apart from
classifying them as whether or not they are Turing complete.
I doubt anyone here would argue with the opinion that Lisp is "more
powerful" than C, but in fact they are both Turing complete and
therefore equivalent in power. Thus the ranking of Lisp above C is
really based on something else. Ease of abstraction, ease of
formulation and support for the programmer are perhaps closer to the
actual criteria, but none of these necessarily equate to additional
power. Nor do first class functions, higher order functions,
reflection, metaprogramming, etc., ad nauseam.
Chomsky ranks (classes of) languages according to the complexity of
their grammar - which affects the potential complexity of their
syntax. Power is a function of semantics and semantics are dependent
on syntactical complexity ... obviously there must be sufficient
complexity to be able to distinguish different semantics. But Lisp is
an existence proof that the syntactic complexity required to achieve
Turing completeness is quite low.
>Maybe I've said it well enough that someone can clean it up and re-ask
>it. :) But it seems to be the question that vexxes marketeers--i.e.,
>how do I explain to someone why buying x or y paradigm adds "power"
>other than just "telling success stories"...?
>
>> Perhaps this is what you (Kent) and Matthias and Rob were getting at
>> all along. But then it doesn't make sense either to talk about Common
>> Lisp as a distinct language because it can be any language.
>>
>> Also, I was not discussing CL in particular but rather sexpr based
>> languages which resemble Lisp in notation. I understand that that was
>> not made clear, and for that, I apologize.
>
>No harm done, and no apology needed from my point of view, but I do
>appreciate the clarification of intent just to put the discussion into
>context.
George
--
for email reply remove "/" from address
George Neuner <·········@comcast.net> wrote:
+---------------
| Kent M Pitman <······@nhplace.com> wrote:
| >Actually, I wish there were some notation of "grammatical complexity"
| >that was different than mere syntax-tokenization and grouping, which
| >I might call "syntactic complexity".
|
| I'm not sure there is much literature on this topic pertaining to
| programming ...
+---------------
Here's the main one I remember reading [but it's from 16 years ago!!]:
ftp://ftp.cs.indiana.edu/pub/scheme-repository/doc/pubs/express.ps.gz
http://www.cs.rice.edu/CS/PLT/Publications/Scheme/scp91-felleisen.ps.gz
Matthias Felleisen, "On the Expressive Power of Programming Languages",
Science of Computer Programming, 1991.
Abstract
The literature on programming languages contains an abundance
of informal claims on the relative expressive power of
programming languages, but there is no framework for formalizing
such statements nor for deriving interesting consequences.
As a first step in this direction, we develop a formal notion
of expressiveness and investigate its properties. To validate
the theory, we analyze some widely held beliefs about the
expressive power of several extensions of functional languages.
Based on these results, we believe that our system correctly
captures many of the informal ideas on expressiveness, and
that it constitutes a foundation for further research in this
direction.
-Rob
-----
Rob Warnock <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
On Sep 7, 3:34 am, Kent M Pitman <······@nhplace.com> wrote:
> George Neuner <·········@comcast.net> writes:
> > >Terminology: You mean to say "pre-defined Lisp syntax". The stuff written
> > >by users is _still_ Lisp syntax.
>
> > Sort of. What I mean exactly is any sexpr syntax that conforms to
> > Lisp's prefix notation.
>
> Well, except that this may be useful for some special-purpose one-off
> thing, since virtually anything may be useful to a thing, but in terms
> of "describing CL", it's not meaningful to say "handles things people
> might write who have no pre-defined agreement with you" other than to
> say "the full set of things people might write".
>
> I asked earlier, I think, or maybe I started to ask and then didn't
> send it, so I'll ask again: what would one do differently if one had a
> parser for this allegedly interesting subset? Is there a goal here
> that is logically distinct from discussing what the set of numeric
> values Lisp could compute if bignums were not there? The reader does
> define readmacros so I don't see quite what people are getting at in
> discussing the properties of the reader absent readmacros.
If the discussion here is about writing something to parse Common
Lisp, then I agree with your implication here Kent that this is a
pretty pointless discussion. The CL reader algorithm is simple, and
obviously isn't reducable to any sub-Turing class of parsers.
However, CL is not the only interesting Lisp language. If I'm not
tripping, ISLISP doesn't have an extensible reader, which means that
its program texts can fall into some less powerful class of parsers.
The question of whether ISLISP is LL(n) might be worth wondering
about.
"Thomas F. Burdick" <········@gmail.com> writes:
> If I'm not tripping, ISLISP doesn't have an extensible reader, which
> means that its program texts can fall into some less powerful class
> of parsers. The question of whether ISLISP is LL(n) might be worth
> wondering about.
Yes, I don't recall it coming up for explicit discussion, so I'd hesitate
to go very far in trying to assert overt intent of any kind on this but
my personal sense is that it would be fair to say the group treated the
design more similarly to Scheme in that it blurred the "defined on structure"
vs "defined on text" issue in a neutral way. Since it didn't come up
explicitly that I remember, for all I know, some people/organizations/countries
did think one thing or the other and not all disagreed, which is entirely
possible in such groups.
But it's quite fair to say that this issue matters to other Lisp dialects
(or even to subsets of CL). Any discussion thus framed which someone felt
useful would not be one I'd want to dissuade. I just was trying to avoid the
notion that CL was accidentally characterized as "LL(1)" (or n>1) without a
clear understanding that this leaves out material details. And my main reason
for wanting to clearly make that point is that I think those details are not
well-known to everyone and lack of such clear framing can entrench
misconceptions rather than peel them back.
George Neuner <·········@comcast.net> writes:
> On Wed, 5 Sep 2007 00:04:04 +0200, "Thomas" <·······@o2.pl> wrote:
>
> As an open question to Matthias or whoever, I don't really see how
> readtable handling would materially affect the parser's LL complexity.
> Macro character parsing itself is LL(1) and it would be subsumed by
> the greater complexity of parsing the forms. What is the extra
> complexity?
Well, I'm pretty sure I have, in the past, made a readtable that
redefines every single character to be the same readmacro (one that
trampolines to another parser, for example, to implement a readmacro
that implements a FORTRAN parser... though it could have been any kind
of parser once the readmacro got control. That's how CGOL worked to
add infix syntax to MACLISP). Since I could then trampoline to a
parser of any nature whatsoever, that means that once a readmacro is
in play, you can really make no statements about the parser's nature.
It is for this reason that I generally don't refer to Lisp's reader as
a parser, and even when I do use the parse metaphor, I try not to
refer to a notion of a grammar as what drives it. I feel like it just
sets people on the path to ask a bunch of questions the answers to
which will mostly mislead them into a wrong model of what's going on.
On 05 Sep 2007 20:53:13 -0400, Kent M Pitman <······@nhplace.com>
wrote:
>George Neuner <·········@comcast.net> writes:
>
>> On Wed, 5 Sep 2007 00:04:04 +0200, "Thomas" <·······@o2.pl> wrote:
>>
>> As an open question to Matthias or whoever, I don't really see how
>> readtable handling would materially affect the parser's LL complexity.
>> Macro character parsing itself is LL(1) and it would be subsumed by
>> the greater complexity of parsing the forms. What is the extra
>> complexity?
>
>Well, I'm pretty sure I have, in the past, made a readtable that
>redefines every single character to be the same readmacro (one that
>trampolines to another parser, for example, to implement a readmacro
>that implements a FORTRAN parser... though it could have been any kind
>of parser once the readmacro got control. That's how CGOL worked to
>add infix syntax to MACLISP). Since I could then trampoline to a
>parser of any nature whatsoever, that means that once a readmacro is
>in play, you can really make no statements about the parser's nature.
Ok, that makes sense. I was only thinking about Lisp syntax and what
extra was necessary for dispatching. I forgot that the handler might
do anything once it got control.
>It is for this reason that I generally don't refer to Lisp's reader as
>a parser, and even when I do use the parse metaphor, I try not to
>refer to a notion of a grammar as what drives it. I feel like it just
>sets people on the path to ask a bunch of questions the answers to
>which will mostly mislead them into a wrong model of what's going on.
Also sensible.
George
--
for email reply remove "/" from address
George Neuner wrote:
> What is the extra complexity?
For example, a macro dispatch function for the character #\[ that reads
words of the form wWw, where W is the reverse of w, in square brackets
in the input stream, and produces an error for words (within square
brackets) that are not of that form.
That is, for example, [abbaab] is valid, but [ababab] produces an error.
This language is not context free (which can be shown by applying the
Pumping Lemma for context-free languages) and hence it can't be handled
by a parser for (a subset of) context-free languages, such as an
LL/LR-parser.
Thomas wrote:
> I just read the definition of LL parser, and have to write the lisp
> interpreter. Is LL(1) parser enought for lisp language ?
Not if you include readtables...