I'm a compiler newbie and curious if Python grammar is able to
be parsed by a recursive descent parser or if it requires
a more powerful algorithm.
Chris 9 3324 se******@spawar .navy.mil wrote:
I'm a compiler newbie and curious if Python grammar is able to
be parsed by a recursive descent parser or if it requires
a more powerful algorithm.
Python is relatively simple to parse using a recursive descent parser. If
you're rolling your own as a learning exercise, the grammar for python is
included in one of the top level directories of the source distribution for
python.
The one area that is slightly different from usual is the emitting of INDENT
and DEDENT tokens by the lexer due to handling of whitespace. But that's
not really that complex either.
A couple of years ago I decided to see what it would be like to try to parse
a python-like language with no keywords and to see if you could do it test
first (for fun :). If you do this, you discover the grammar is very short
but you need terminator tokens to close if..elif...elif ...else... like
statements (eg if..elif...elif ...else...end,
try...except... except...except ...endtry).
I put that code up here: http://cerenity.org/SWP/ if you're curious.
That and the python grammar file should probably help you roll your own
parser. (It emits an AST that assumes everything is a function. I was
pondering giving it a lisp backend or transforming to lisp but never
got a round tuit)
If however you're doing this because you're not aware of the compiler
module, it's worth knowing that compiler.parse is a pretty useful
function :-)
Michael. se******@spawar .navy.mil schrieb:
I'm a compiler newbie and curious if Python grammar is able to
be parsed by a recursive descent parser or if it requires
a more powerful algorithm.
I might be mistaken, but isn't recursive descent one of the more
powerful parsing techniques - for the price of non-linearity and even
potentially non-termination?
Under that assumption: certainly!
Diez
In message <4o************ @uni-berlin.de>, Diez B. Roggisch wrote: se******@spawar .navy.mil schrieb:
>I'm a compiler newbie and curious if Python grammar is able to be parsed by a recursive descent parser or if it requires a more powerful algorithm.
I might be mistaken, but isn't recursive descent one of the more
powerful parsing techniques - for the price of non-linearity and even
potentially non-termination?
No, you're thinking of LR(k) bottom-up parsers. Recursive descent is a
top-down parser--might be the same thing as LL(1), I'm not sure. It's easy
to implement and easy to understand, to the point where there is strong
pressure on programming-language designers to make sure their languages can
be parsed with recursive descent.
At Thursday 28/9/2006 17:00, Michael wrote:
>se******@spawa r.navy.mil wrote:
I'm a compiler newbie and curious if Python grammar is able to
be parsed by a recursive descent parser or if it requires
a more powerful algorithm.
Python is relatively simple to parse using a recursive descent parser. If you're rolling your own as a learning exercise, the grammar for python is included in one of the top level directories of the source distribution for python.
And it will stay so. From PEP 3099: "The parser won't be more complex
than LL(1). Simple is better than complex. This idea extends to the
parser. Restricting Python's grammar to an LL(1) parser is a
blessing, not a curse. It puts us in handcuffs that prevent us from
going overboard and ending up with funky grammar rules like some
other dynamic languages that will go unnamed, like Perl."
Gabriel Genellina
Softlab SRL
_______________ _______________ _______________ _____
Preguntá. Respondé. Descubrí.
Todo lo que querías saber, y lo que ni imaginabas,
está en Yahoo! Respuestas (Beta).
¡Probalo ya! http://www.yahoo.com.ar/respuestas
Lawrence D'Oliveiro wrote:
In message <4o************ @uni-berlin.de>, Diez B. Roggisch wrote:
>se******@spawar .navy.mil schrieb:
>>I'm a compiler newbie and curious if Python grammar is able to be parsed by a recursive descent parser or if it requires a more powerful algorithm.
I might be mistaken, but isn't recursive descent one of the more powerful parsing techniques - for the price of non-linearity and even potentially non-termination?
No, you're thinking of LR(k) bottom-up parsers. Recursive descent is a
No, I'm not.
top-down parser--might be the same thing as LL(1), I'm not sure. It's easy
to implement and easy to understand, to the point where there is strong
pressure on programming-language designers to make sure their languages
can be parsed with recursive descent.
http://en.wikipedia.org/wiki/Recursive_descent_parser
"""
Recursive descent with backup is a technique that determines which
production to use by trying each production in turn. Recursive descent with
backup is not limited to LL(k) grammars, but is not guaranteed to terminate
unless the grammar is LL(k). Even when they terminate, parsers that use
recursive descent with backup may require exponential time.
"""
I have to admit that I have difficulties to compare LR(k) to recursive
descent, but the fact that the latter contains backtracking makes it at
least more powerful than LL(k)
Diez
In message <4o************ @uni-berlin.de>, Diez B. Roggisch wrote:
I have to admit that I have difficulties to compare LR(k) to recursive
descent, but the fact that the latter contains backtracking makes it at
least more powerful than LL(k)
LR(k) is more powerful than LL(k).
>>>>"Diez B. Roggisch" <de***@nospam.w eb.de(DBR) wrote:
>DBRhttp://en.wikipedia.org/wiki/Recursive_descent_parser
>DBR""" DBRRecursive descent with backup is a technique that determines which DBRproductio n to use by trying each production in turn. Recursive DBRdescent with backup is not limited to LL(k) grammars, but is not DBRguarantee d to terminate unless the grammar is LL(k). Even when they DBRterminate , parsers that use recursive descent with backup may require DBRexponenti al time. DBR"""
This is the first time I see this called `backup'. I have always used and
seen the term `backtracking'.
--
Piet van Oostrum <pi**@cs.uu.n l>
URL: http://www.cs.uu.nl/~piet [PGP 8DAE142BE17999C 4]
Private email: pi**@vanoostrum .org
Lawrence D'Oliveiro schrieb:
In message <4o************ @uni-berlin.de>, Diez B. Roggisch wrote:
>I have to admit that I have difficulties to compare LR(k) to recursive descent, but the fact that the latter contains backtracking makes it at least more powerful than LL(k)
LR(k) is more powerful than LL(k).
I know _that_, the point was that recursive descent is more power full
than LL(k)
Diez
On 10/6/06, Diez B. Roggisch <de***@nospam.w eb.dewrote:
Lawrence D'Oliveiro schrieb:
In message <4o************ @uni-berlin.de>, Diez B. Roggisch wrote:
I have to admit that I have difficulties to compare LR(k) to recursive
descent, but the fact that the latter contains backtracking makes it at
least more powerful than LL(k)
LR(k) is more powerful than LL(k).
I know _that_, the point was that recursive descent is more power full
than LL(k)
Correct me if I'm wrong, but recursive descent parsers are top-down, yes?
Parse::RecDesce nt in Perl is a top-down parser. It can even do some
context-sensitive grammars and can almost certainly handle Python.
Is Python context-free? Not sure. Does left parenthesis opening either
a function call (x) or an empty tuple () count as context-sensitive,
for instance? Or can () be considered a terminal symbol unto itself?
I am new to most of this :)
-- Theerasak This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics |
by: Magnus Lie Hetland |
last post by:
Hi!
I've been looking at ways of dealing with nested structures in regexps
(becuase I figured that would be faster than the Python parsing code
I've currently got) and came across a few interesting things...
First there is this, mentioning the (?<DEPTH>) and (?<-DEPTH>)
constructs of the .NET regexp matcher:
http://www.rassoc.com/gregr/weblog/archive.aspx?post=590
|
by: Phil |
last post by:
Hello
I'm trying to display all DIV tags of a document :
Example :
+ <DIV id="1">
- <DIV id="1-1"></DIV>
</DIV>
+ <DIV id="2">
- <DIV id="2-1"></DIV>
|
by: Phlip |
last post by:
C++ newsgroupies:
I wrote a parser to solve math expressions like "3.0 ^(4 - 5)", or "3 / 8".
Below my sig is recursiveDescentParser.cpp, the test suite that drove the
implementation of the expression solver found in recursiveDescentParser.h,
in a parallel post.
Test-Driven Development works by accumulating assertions. Before the very
first assertion existed...
|
by: Phlip |
last post by:
C++ newsgroupies:
I wrote a parser to solve math expressions like "3.0 ^(4 - 5)", or "3 / 8".
It's bad luck to name an interface after its implementation. This file could
have been "expressionSolver.h". But naturally, if I set out to implement
recursive descent parsing, that tainted my filename selection.
Below my sig is recursiveDescentParser.h, a math expression solver. Using
the test framework, and test suite appearing in parallel...
|
by: BQ |
last post by:
Due to a lack of resources, I have to translate the following recursive
function in its iterative form.
It's a kind of dichotomic search.
void SearchSlaves(unsigned long start_uid, unsigned long end_uid)
{
char ret;
//ping over a range of addresses (all slaves with uid in the range from
start_uid to end_uid will reply)
ret = PingSlave(start_uid,end_uid);
| |
by: seberino |
last post by:
I'm a compiler newbie and was curious if Python's language/grammar
can be handled by a recursive descent parser.
Well?
Chris
|
by: sebastien.abeille |
last post by:
Hello,
I would like to create a minimalist file browser using pyGTK.
Having read lot of tutorials, it seems to me that that in my case, the
best solution is
to have a gtk.TreeStore containing all the files and folders so that
it would map the
file system hierarchy.
|
by: Martin Marcher |
last post by:
Hello,
I'm playing around with os.walk and I made up del_tree(path) which I
think is correct (in terms of the algorithm, but not as python wants
it :)).
As soon as some directory is deleted the iterator of os.walk chokes.
OK that is somehow clear to me as it can't be valid anymore since it
can't go to the just deleted directory but it is in the iterator.
|
by: Just Another Victim of the Ambient Morality |
last post by:
Is pyparsing really a recursive descent parser? I ask this because
there are grammars it can't parse that my recursive descent parser would
parse, should I have written one. For instance:
from pyparsing import *
grammar = OneOrMore(Word(alphas)) + Literal('end')
grammar.parseString('First Second Third end')
|
by: Hystou |
last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can effortlessly switch the default language on Windows 10 without reinstalling. I'll walk you through it.
First, let's disable language synchronization. With a Microsoft account, language settings sync across devices. To prevent any complications,...
|
by: Oralloy |
last post by:
Hello folks,
I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>".
The problem is that using the GNU compilers, it seems that the internal comparison operator "<=>" tries to promote arguments from unsigned to signed.
This is as boiled down as I can make it.
Here is my compilation command:
g++-12 -std=c++20 -Wnarrowing bit_field.cpp
Here is the code in...
| |
by: tracyyun |
last post by:
Dear forum friends,
With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each protocol has its own unique characteristics and advantages, but as a user who is planning to build a smart home system, I am a bit confused by the choice of these technologies. I'm particularly interested in Zigbee because I've heard it does some...
|
by: agi2029 |
last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing, and deployment—without human intervention. Imagine an AI that can take a project description, break it down, write the code, debug it, and then launch it, all on its own....
Now, this would greatly impact the work of software developers. The idea...
|
by: isladogs |
last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM).
In this session, we are pleased to welcome a new presenter, Adolph Dupré who will be discussing some powerful techniques for using class modules.
He will explain when you may want to use classes instead of User Defined Types (UDT). For example, to manage the data in unbound forms.
Adolph will...
|
by: TSSRALBI |
last post by:
Hello
I'm a network technician in training and I need your help.
I am currently learning how to create and manage the different types of VPNs and I have a question about LAN-to-LAN VPNs.
The last exercise I practiced was to create a LAN-to-LAN VPN between two Pfsense firewalls, by using IPSEC protocols.
I succeeded, with both firewalls in the same network. But I'm wondering if it's possible to do the same thing, with 2 Pfsense firewalls...
|
by: adsilva |
last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
|
by: 6302768590 |
last post by:
Hai team
i want code for transfer the data from one system to another through IP address by using C# our system has to for every 5mins then we have to update the data what the data is updated we have to send another system
| |
by: bsmnconsultancy |
last post by:
In today's digital era, a well-designed website is crucial for businesses looking to succeed. Whether you're a small business owner or a large corporation in Toronto, having a strong online presence can significantly impact your brand's success. BSMN Consultancy, a leader in Website Development in Toronto offers valuable insights into creating effective websites that not only look great but also perform exceptionally well. In this comprehensive...
| |