On 25 September 2000, Barry A. Warsaw said:

I've been wanting to check out Antlr (www.antlr.org) because it gives us the /possibility/ to use the same grammar files for both CPython and JPython. One problem though is that it generates Java and C++ so we'd be accepting our first C++ into the core if we went this route.

Or contribute a C back-end to ANTLR -- I've been toying with this idea for, ummm, too damn long now. Years. Greg

On 25 September 2000, Barry A. Warsaw said:

NS> How different are PCCTS and ANTLR? Perhaps we could use PCCTS NS> for CPython and ANTLR for JPython.

Unknown. It would only make sense if the same grammar files could be fed to each. I have no idea whether that's true or not. If not, Greg's idea is worth researching.

PCCTS 1.x grammar files tend to have lots of C code interwoven in them -- at least for tricky, ill-defined grammars like BibTeX. ;-) ANTLR 2.x grammars certainly allow Java code to be woven into them; I assume you can instead weave C++ or Sather if that's your preference. Obviously, this would be one problem with having a common grammar for JPython and CPython. Greg

Yes, but why not YACC? Is Antlr so much better, or is YACC too primitive, or what? IMHO, adding C++ just for parsing is not going to happen, so Antlr is not going to happen either.

I think the advantage that Barry saw is that ANTLR generates Java in addition to C, so it could be used in JPython as well. In addition, ANTLR is more advanced than YACC; it specifically supports full EBNF as input, and has better mechanisms for conflict resolution. On the YACC for Java side, Axel Schreiner has developed jay, see http://www2.informatik.uni-osnabrueck.de/bernd/jay/staff/design/de/Artikel.h... (if you read German, otherwise don't bother :-) The main problem with multilanguage output is the semantic actions - it would be quite a stunt to put semantic actions into the parser which are valid both in C and Java :-) On that front, there is also CUP (http://www.cs.princeton.edu/~appel/modern/java/CUP/), which has different markup for Java actions ({: ... :}). There is also BYACC/J, a patch to Berkeley Yacc to produce Java (http://www.lincom-asg.com/~rjamison/byacc/). Personally, I'm quite in favour of having the full parser source (including parser generator if necessary) in the Python source distribution. As a GCC contributor, I know what pain it is for users that GCC requires bison to build - even though it is only required for CVS builds, as distributions come with the generated files. Regards, Martin

Martin von Loewis wrote:

...

Yes, but why not YACC? Is Antlr so much better, or is

I think the advantage that Barry saw is that ANTLR generates Java in addition to C, so it could be used in JPython as well. In addition, ANTLR is more advanced than YACC; it specifically supports full EBNF as input, and has better mechanisms for conflict resolution.

Oh, OK. Thanks.

Personally, I'm quite in favour of having the full parser source (including parser generator if necessary) in the Python source distribution. As a GCC contributor, I know what pain it is for users that GCC requires bison to build - even though it is only required for CVS builds, as distributions come with the generated files.

I see your point, but the practical solution that we can do today is to use YACC, bison, and distribute the generated parser files. Jim

I don't understand what problem this is a practical solution to. This thread started with MAL's questions about finding errors in Python code. You mentioned an effort to write a lint-like tool. It may be that YACC has great support for error recovery, in which case MAL might want to look at for his tool.

But in general, the most practical solution for parsing Python is probably to use the Python parser and the builtin parser module. It already exists and seems to work just fine.

Probably not that relevant any more, but MAL originally asked for a parser that doesn't stop at the first error. That's a real weakness of the existing parser!!! --Guido van Rossum (home page: http://www.pythonlabs.com/~guido/)

On Tue, 26 Sep 2000, Greg Ewing wrote:

Guido:

...

MAL originally asked for a parser that doesn't stop at the first error. That's a real weakness of the existing parser!!!

Is it really worth putting a lot of effort into this?

It might be if you were trying to develop an IDE that could syntactically analyse what the user was typing even if he/she had left a half finished expression further up in the buffer (I'd kind of assumed this was the goal). So you're not continuing after errors, exactly, more like unfinishednesses (or some better word...). I guess one approach to this would be to divided up the buffer according to indentation and then parse each block as delimited by the indentation individually. Two random points: 1) Triple-quoted strings are going to be a problem. 2) Has anyone gotten flex to tokenize Python? I was looking at the manual yesterday and it didn't look impossible, although a bit tricky. Cheers, M.

Jeremy Hylton wrote:

I don't understand what problem this is a practical solution to.

To recover from errors better by using YACC's built-in error recovery features. Maybe unifying the C and Java parsers. I admit I don't know how J-Python parses Python. I kind of threw in my objection to tokenize.py which should be combined with tokenizer.c. Of course it is work which only results in the same operation as before, but reduces the code base. Not a popular project.

But in general, the most practical solution for parsing Python is probably to use the Python parser and the builtin parser module. It already exists and seems to work just fine.

A very good point. I am not 100% sure it is worth it. But I found the current parser unworkable for my project. JimA

...

...

...

...

"JCA" == James C Ahlstrom writes:

JCA> The following is based on trying (a great learning experience) JCA> to write a better Python lint. JCA> There are IMHO two problems with the current Python grammar JCA> file. It is not possible to express operator precedence, so JCA> deliberate shift/reduce conflicts are used instead. That makes JCA> the parse tree complicated and non intuitive. And there is no JCA> provision for error productions. YACC has both of these as JCA> built-in features. JCA> I also found speed problems with tokenize.py. AFAIK, it only JCA> exists because tokenizer.c does not provide comments as tokens, JCA> but eats them instead. We could modify tokenizer.c, then make JCA> tokenize.py be the interface to the fast C tokenizer. This JCA> eliminates the problem of updating both too. JCA> So how about re-writing the Python grammar in YACC in order to JCA> use its more advanced features?? The simple YACC grammar I JCA> wrote for 1.5.2 plus an altered tokenizer.c parsed the whole JCA> Lib/*.py in a couple seconds vs. 30 seconds for the first file JCA> using Aaron Watters' Python lint grammar written in Python. Why not use the actual Python parser instead of tokenize.py? I assume it is also faster than Aaron's Python lint grammer written in Python. The compiler in Tools/compiler uses the parser module internally and produces an AST that is straightforward to use. (The parse tree produced by the parser module is fairly low-level.) There was a thread (on the compiler-sig, I believe) where Moshe and I noodled with a simple lint-like warnings framework based on the compiler package. I don't have the code we ended up with, but I found an example checker in the mail archives and have included it below. It checks for NameErrors. I believe one useful change that Moshe and I arrived at was to avoid the explicit stack that the code uses (via enterNamespace and exitNamespace) and instead pass the namespace as an optional extra argument to the visitXXX methods. Jeremy """Check for NameErrors""" from compiler import parseFile, walk from compiler.misc import Stack, Set import __builtin__ from UserDict import UserDict class Warning: def __init__(self, filename, funcname, lineno): self.filename = filename self.funcname = funcname self.lineno = lineno def __str__(self): return self._template % self.__dict__ class UndefinedLocal(Warning): super_init = Warning.__init__ def __init__(self, filename, funcname, lineno, name): self.super_init(filename, funcname, lineno) self.name = name _template = "%(filename)s:%(lineno)s " \ "%(funcname)s undefined local %(name)s" class NameError(UndefinedLocal): _template = "%(filename)s:%(lineno)s " \ "%(funcname)s undefined name %(name)s" class NameSet(UserDict): """Track names and the line numbers where they are referenced""" def __init__(self): self.data = self.names = {} def add(self, name, lineno): l = self.names.get(name, []) l.append(lineno) self.names[name] = l class CheckNames: def __init__(self, filename): self.filename = filename self.warnings = [] self.scope = Stack() self.gUse = NameSet() self.gDef = NameSet() # _locals is the stack of local namespaces # locals is the top of the stack self._locals = Stack() self.lUse = None self.lDef = None self.lGlobals = None # var declared global # holds scope,def,use,global triples for later analysis self.todo = [] def enterNamespace(self, node): self.scope.push(node) self.lUse = use = NameSet() self.lDef = _def = NameSet() self.lGlobals = gbl = NameSet() self._locals.push((use, _def, gbl)) def exitNamespace(self): self.todo.append((self.scope.top(), self.lDef, self.lUse, self.lGlobals)) self.scope.pop() self._locals.pop() if self._locals: self.lUse, self.lDef, self.lGlobals = self._locals.top() else: self.lUse = self.lDef = self.lGlobals = None def warn(self, warning, funcname, lineno, *args): args = (self.filename, funcname, lineno) + args self.warnings.append(apply(warning, args)) def defName(self, name, lineno, local=1): if self.lUse is None: self.gDef.add(name, lineno) elif local == 0: self.gDef.add(name, lineno) self.lGlobals.add(name, lineno) else: self.lDef.add(name, lineno) def useName(self, name, lineno, local=1): if self.lUse is None: self.gUse.add(name, lineno) elif local == 0: self.gUse.add(name, lineno) self.lUse.add(name, lineno) else: self.lUse.add(name, lineno) def check(self): for s, d, u, g in self.todo: self._check(s, d, u, g, self.gDef) # XXX then check the globals def _check(self, scope, _def, use, gbl, globals): # check for NameError # a name is defined iff it is in def.keys() # a name is global iff it is in gdefs.keys() gdefs = UserDict() gdefs.update(globals) gdefs.update(__builtin__.__dict__) defs = UserDict() defs.update(gdefs) defs.update(_def) errors = Set() for name in use.keys(): if not defs.has_key(name): firstuse = use[name][0] self.warn(NameError, scope.name, firstuse, name) errors.add(name) # check for UndefinedLocalNameError # order == use & def sorted by lineno # elements are lineno, flag, name # flag = 0 if use, flag = 1 if def order = [] for name, lines in use.items(): if gdefs.has_key(name) and not _def.has_key(name): # this is a global ref, we can skip it continue for lineno in lines: order.append((lineno, 0, name)) for name, lines in _def.items(): for lineno in lines: order.append((lineno, 1, name)) order.sort() # ready contains names that have been defined or warned about ready = Set() for lineno, flag, name in order: if flag == 0: # use if not ready.has_elt(name) and not errors.has_elt(name): self.warn(UndefinedLocal, scope.name, lineno, name) ready.add(name) # don't warn again else: ready.add(name) # below are visitor methods def visitFunction(self, node, noname=0): for expr in node.defaults: self.visit(expr) if not noname: self.defName(node.name, node.lineno) self.enterNamespace(node) for name in node.argnames: self.defName(name, node.lineno) self.visit(node.code) self.exitNamespace() return 1 def visitLambda(self, node): return self.visitFunction(node, noname=1) def visitClass(self, node): for expr in node.bases: self.visit(expr) self.defName(node.name, node.lineno) self.enterNamespace(node) self.visit(node.code) self.exitNamespace() return 1 def visitName(self, node): self.useName(node.name, node.lineno) def visitGlobal(self, node): for name in node.names: self.defName(name, node.lineno, local=0) def visitImport(self, node): for name, alias in node.names: self.defName(alias or name, node.lineno) visitFrom = visitImport def visitAssName(self, node): self.defName(node.name, node.lineno) def check(filename): global p, checker p = parseFile(filename) checker = CheckNames(filename) walk(p, checker) checker.check() for w in checker.warnings: print w if __name__ == "__main__": import sys # XXX need to do real arg processing check(sys.argv[1])