From 0588d19abef62dad63a7794a37bdd6a71c526d9e Mon Sep 17 00:00:00 2001 From: Patrick Georgi Date: Wed, 12 Aug 2009 15:00:51 +0000 Subject: Kconfig! Works on Kontron, qemu, and serengeti. Signed-off-by: Patrick Georgi tested on abuild only. Acked-by: Ronald G. Minnich git-svn-id: svn://svn.coreboot.org/coreboot/trunk@4534 2b7e53f0-3cfb-0310-b3e9-8179ed1497e1 --- util/sconfig/LICENSE | 18 + util/sconfig/Makefile | 31 ++ util/sconfig/NOTES | 46 ++ util/sconfig/config.g | 1029 ++++++++++++++++++++++++++++++++++++++ util/sconfig/parsedesc.g | 196 ++++++++ util/sconfig/test.config | 6 + util/sconfig/yapps2.py | 779 +++++++++++++++++++++++++++++ util/sconfig/yapps2.tex | 1225 ++++++++++++++++++++++++++++++++++++++++++++++ util/sconfig/yappsrt.py | 172 +++++++ 9 files changed, 3502 insertions(+) create mode 100644 util/sconfig/LICENSE create mode 100644 util/sconfig/Makefile create mode 100644 util/sconfig/NOTES create mode 100644 util/sconfig/config.g create mode 100644 util/sconfig/parsedesc.g create mode 100644 util/sconfig/test.config create mode 100644 util/sconfig/yapps2.py create mode 100644 util/sconfig/yapps2.tex create mode 100644 util/sconfig/yappsrt.py (limited to 'util/sconfig') diff --git a/util/sconfig/LICENSE b/util/sconfig/LICENSE new file mode 100644 index 0000000..64f38b8 --- /dev/null +++ b/util/sconfig/LICENSE @@ -0,0 +1,18 @@ +Permission is hereby granted, free of charge, to any person obtaining +a copy of this software and associated documentation files (the +"Software"), to deal in the Software without restriction, including +without limitation the rights to use, copy, modify, merge, publish, +distribute, sublicense, and/or sell copies of the Software, and to +permit persons to whom the Software is furnished to do so, subject to +the following conditions: + +The above copyright notice and this permission notice shall be included +in all copies or substantial portions of the Software. + +THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, +EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF +MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. +IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY +CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, +TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE +SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. diff --git a/util/sconfig/Makefile b/util/sconfig/Makefile new file mode 100644 index 0000000..3328380 --- /dev/null +++ b/util/sconfig/Makefile @@ -0,0 +1,31 @@ +ALL: $(shell echo *.g | sed s/\\.g/\\.py/g ) + +%.py: %.g yapps2.py yappsrt.py Makefile + python yapps2.py $< + +DOC: yapps2.ps yapps2.pdf manual/index.html + +yapps2.ps: yapps2.dvi + dvips -q yapps2.dvi -o yapps2.ps + +yapps2.pdf: yapps2.ps + ps2pdf yapps2.ps + +yapps2.dvi: yapps2.tex + latex yapps2.tex + +manual/index.html: yapps2.aux yapps2.tex + rm manual/yapps2.css + latex2html -dir 'manual' -mkdir -lcase_tags -font_size 12pt -split 4 -toc_depth 4 -html_version 4.0,unicode,table -t 'Yapps 2.0 Manual' -address 'Amit J Patel, amitp@cs.stanford.edu' -info 0 -show_section_numbers -up_title 'Yapps Page' -up_url 'http://theory.stanford.edu/~amitp/yapps/' -strict -image_type png yapps2.tex + echo '@import url("http://www-cs-students.stanford.edu/~amitp/amitp.css");' > manual/yapps2-new.css + echo 'hr { display:none; }' >> manual/yapps2-new.css + echo 'h1 br, h2 br { display:none; }' >>manual/yapps2-new.css + cat manual/yapps2.css >> manual/yapps2-new.css + rm manual/yapps2.css + mv manual/yapps2-new.css manual/yapps2.css + +DISTRIB: + cd ..; zip -u yapps2.zip yapps2/{LICENSE,yapps2.py,yappsrt.py,parsedesc.g,examples/*.g,NOTES,yapps2.tex,Makefile,manual/*.html,manual/*.css,manual/*.png} + +clean: + rm -f config.py yappsrt.pyc parsedesc.py diff --git a/util/sconfig/NOTES b/util/sconfig/NOTES new file mode 100644 index 0000000..325e76a --- /dev/null +++ b/util/sconfig/NOTES @@ -0,0 +1,46 @@ +April 14, 2002: + +I haven't worked on Yapps for a while, mainly because I spent all my energy +on trying to graduate. Now that I've finished school, I have several projects +I want to start working on again, including Yapps. + +Notes for myself: + +Add a debugging mode that helps you understand how the grammar + is constructed and how things are being parsed +Look into an English output mode that would use natural language + to describe a grammar +Optimize unused variables +Add a convenience to automatically gather up the values returned + from subpatterns, put them into a list, and return them +Improve the documentation +Write some larger examples +Get rid of old-style regex support +Use SRE's lex support to speed up lexing (this may be hard given that + yapps allows for context-sensitive lexers) +Look over Dan Connoly's experience with Yapps (bugs, frustrations, etc.) + and see what improvements could be made +Add something to pretty-print the grammar (without the actions) +Maybe conditionals? Follow this rule only if holds. + But this would be useful mainly when multiple rules match, and we + want the first matching rule. The conditional would mean we skip to + the next rule. Maybe this is part of the attribute grammar system, + where rule X<0> can be specified separately from X. +Convenience functions that could build return values for all rules + without specifying the code for each rule individually +Patterns (abstractions over rules) -- for example, comma separated values + have a certain rule pattern that gets replicated all over the place +"Gather" mode that simply outputs the return values for certain nodes. + For example, if you just want all expressions, you could ask yapps + to gather the results of the 'expr' rule into a list. This would + ignore all the higher level structure. +Look at everyone's Yapps grammars, and come up with larger examples + http://www.w3.org/2000/10/swap/SemEnglish.g + http://www.w3.org/2000/10/swap/kifExpr.g + http://www.w3.org/2000/10/swap/rdfn3.g +It would be nice if you could feed text into Yapps (push model) instead + of Yapps reading text out of a string (pull model). However, I think + that would make the resulting parser code mostly unreadable + (like yacc, etc.). Coroutines/stacklesspython may be the answer. + + diff --git a/util/sconfig/config.g b/util/sconfig/config.g new file mode 100644 index 0000000..db3c516 --- /dev/null +++ b/util/sconfig/config.g @@ -0,0 +1,1029 @@ +# -*- python -*- +import sys +import os +import re +import string +import types + +import traceback + +warnings = 0 +errors = 0 + +treetop = '' +full_mainboard_path = '' +mainboard_path = '' +romimages = {} +curimage = 0 + +# ----------------------------------------------------------------------------- +# Utility Classes +# ----------------------------------------------------------------------------- + +class stack: + """Used to keep track of the current part or dir""" + class __stack_iter: + def __init__ (self, stack): + self.index = 0 + self.len = len(stack) + self.stack = stack + + def __iter__ (self): + return self + + def next (self): + if (self.index < self.len): + s = self.stack[self.index] + self.index = self.index + 1 + return s + raise StopIteration + + def __init__ (self): + self.stack = [] + + def __len__ (self): + return len(self.stack) + + def __getitem__ (self, i): + return self.stack[i] + + def __iter__ (self): + return self.__stack_iter(self.stack) + + def push(self, part): + self.stack.append(part) + + def pop(self): + try: + return self.stack.pop() + except IndexError: + return 0 + + def tos(self): + try: + return self.stack[-1] + except IndexError: + return 0 + + def empty(self): + return (len(self.stack) == 0) +partstack = stack() + +class debug_info: + none = 0 + gencode = 1 + dumptree = 2 + object = 3 + dict = 4 + statement = 5 + dump = 6 + gengraph = 7 + + def __init__(self, *level): + self.__level = level + + def setdebug(self, *level): + self.__level = level + + def level(self, level): + return level in self.__level + + def info(self, level, str): + if level in self.__level: + print str + +global debug +debug = debug_info(debug_info.none) +#debug = debug_info(debug_info.dumptree) +#debug = debug_info(debug_info.object) +#debug = debug_info(debug_info.gencode) + +# ----------------------------------------------------------------------------- +# Error Handling +# ----------------------------------------------------------------------------- + +def error(string): + """Print error message""" + global errors, loc + errors = errors + 1 + print "===> ERROR: %s" % string + +def fatal(string): + """Print error message and exit""" + error(string) + exitiferrors() + +def warning(string): + """Print warning message""" + global warnings, loc + warnings = warnings + 1 + print "===> WARNING: %s" % string + +def exitiferrors(): + """Exit parser if an error has been encountered""" + if (errors != 0): + sys.exit(1) + +def safe_open(file, mode): + try: + return open(file, mode) + except IOError: + fatal("Could not open file \"%s\"" % file) + +# ----------------------------------------------------------------------------- +# Main classes +# ----------------------------------------------------------------------------- + +class romimage: + """A rom image is the ultimate goal of coreboot""" + def __init__ (self, name): + # name of this rom image + self.name = name + + # instance counter for parts + self.partinstance = 0 + + # chip config files included by the 'config' directive + self.configincludes = {} + + # root of part tree + self.root = 0 + + # Last device built + self.last_device = 0 + + def getname(self): + return self.name + + def addconfiginclude(self, part, path): + setdict(self.configincludes, part, path) + + def getconfigincludes(self): + return self.configincludes + + def getincludefilename(self): + if (self.useinitincludes): + return "crt0.S" + else: + return "crt0_includes.h" + + def newformat(self): + return self.useinitincludes + + def numparts(self): + return self.partinstance + + def newpartinstance(self): + i = self.partinstance + self.partinstance = self.partinstance + 1 + return i + + def setroot(self, part): + self.root = part + + def getroot(self): + return self.root + +class partobj: + """A configuration part""" + def __init__ (self, image, dir, parent, part, type_name, instance_name, chip_or_device): + if (parent): + debug.info(debug.object, "partobj dir %s parent %s part %s" \ + % (dir, parent.instance_name, part)) + else: + debug.info(debug.object, "partobj dir %s part %s" \ + % (dir, part)) + + # romimage that is configuring this part + self.image = image + + # links for static device tree + self.children = 0 + self.prev_sibling = 0 + self.next_sibling = 0 + self.prev_device = 0 + self.next_device = 0 + self.chip_or_device = chip_or_device + + # initializers for static device tree + self.registercode = {} + + # part name + self.part = part + + # type name of this part + self.type_name = type_name + + # directory containing part files + self.dir = dir + + # instance number, used to distinguish anonymous + # instances of this part + self.instance = image.newpartinstance() + debug.info(debug.object, "INSTANCE %d" % self.instance) + + # Name of chip config file (0 if not needed) + self.chipconfig = 0 + + # Flag to indicate that we have generated type + # definitions for this part (only want to do it once) + self.done_types = 0 + + # Path to the device + self.path = "" + + # Resources of the device + self.resoruce = "" + self.resources = 0 + + # Enabled state of the device + self.enabled = 1 + + # Flag if I am a duplicate device + self.dup = 0 + + # If there is a chip.h file, we will create an + # include for it. + if (dir): + chiph = os.path.join(dir, "chip.h") + if (os.path.exists(chiph)): + debug.info(debug.object, "%s has chip at %s" % (self, dir)) + self.addconfig(chiph) + + # If no instance name is supplied then generate + # a unique name + if (instance_name == 0): + self.instance_name = self.type_name + \ + "_dev%d" % self.instance + self.chipinfo_name = "%s_info_%d" \ + % (self.type_name, self.instance) + else: + self.instance_name = instance_name + self.chipinfo_name = "%s_info_%d" % (self.instance_name, self.instance) + + # Link this part into the device list + if (self.chip_or_device == 'device'): + if (image.last_device): + image.last_device.next_device = self + self.prev_device = image.last_device + image.last_device = self + + # Link this part into the tree + if (parent and (part != 'arch')): + debug.info(debug.gencode, "add to parent") + self.parent = parent + # add current child as my sibling, + # me as the child. + if (parent.children): + debug.info(debug.gencode, "add %s (%d) as sibling" % (parent.children.dir, parent.children.instance)) + youngest = parent.children + while(youngest.next_sibling): + youngest = youngest.next_sibling + youngest.next_sibling = self + self.prev_sibling = youngest + else: + parent.children = self + else: + self.parent = self + + def info(self): + return "%s: %s" % (self.part, self.type) + def type(self): + return self.chip_or_device + + def readable_name(self): + name = "" + name = "%s_%d" % (self.type_name, self.instance) + if (self.chip_or_device == 'chip'): + name = "%s %s %s" % (name, self.part, self.dir) + else: + name = "%s %s" % (name, self.path) + return name + + def graph_name(self): + name = "{ {_dev%d|" % self.instance + if (self.part): + name = "%s%s" % (name, self.part) + else: + name = "%s%s" % (name, self.chip_or_device) + if (self.type_name): + name = "%s}|%s}" % (name, self.type_name) + else: + name = "%s}|%s}" % (name, self.parent.type_name) + return name + + def dumpme(self, lvl): + """Dump information about this part for debugging""" + print "%d: %s" % (lvl, self.readable_name()) + print "%d: part %s" % (lvl, self.part) + print "%d: instance %d" % (lvl, self.instance) + print "%d: chip_or_device %s" % (lvl, self.chip_or_device) + print "%d: dir %s" % (lvl,self.dir) + print "%d: type_name %s" % (lvl,self.type_name) + print "%d: parent: %s" % (lvl, self.parent.readable_name()) + if (self.children): + print "%d: child %s" % (lvl, self.children.readable_name()) + if (self.next_sibling): + print "%d: siblings %s" % (lvl, self.next_sibling.readable_name()) + print "%d: registercode " % lvl + for f, v in self.registercode.items(): + print "\t%s = %s" % (f, v) + print "%d: chipconfig %s" % (lvl, self.chipconfig) + print "\n" + + def firstchilddevice(self): + """Find the first device in the children link.""" + kid = self.children + while (kid): + if (kid.chip_or_device == 'device'): + return kid + else: + kid = kid.children + return 0 + + def firstparentdevice(self): + """Find the first device in the parent link.""" + parent = self.parent + while (parent and (parent.parent != parent) and (parent.chip_or_device != 'device')): + parent = parent.parent + if ((parent.parent != parent) and (parent.chip_or_device != 'device')): + parent = 0 + while(parent and (parent.dup == 1)): + parent = parent.prev_sibling + if (not parent): + fatal("Device %s has no device parent; this is a config file error" % self.readable_name()) + return parent + + def firstparentdevicelink(self): + """Find the first device in the parent link and record which link it is.""" + link = 0 + parent = self.parent + while (parent and (parent.parent != parent) and (parent.chip_or_device != 'device')): + parent = parent.parent + if ((parent.parent != parent) and (parent.chip_or_device != 'device')): + parent = 0 + while(parent and (parent.dup == 1)): + parent = parent.prev_sibling + link = link + 1 + if (not parent): + fatal("Device %s has no device parent; this is a config file error" % self.readable_name()) + return link + + + def firstparentchip(self): + """Find the first chip in the parent link.""" + parent = self.parent + while (parent): + if ((parent.parent == parent) or (parent.chip_or_device == 'chip')): + return parent + else: + parent = parent.parent + fatal("Device %s has no chip parent; this is a config file error" % self.readable_name()) + + def firstsiblingdevice(self): + """Find the first device in the sibling link.""" + sibling = self.next_sibling + while(sibling and (sibling.path == self.path)): + sibling = sibling.next_sibling + if ((not sibling) and (self.parent.chip_or_device == 'chip')): + sibling = self.parent.next_sibling + while(sibling): + if (sibling.chip_or_device == 'device'): + return sibling + else: + sibling = sibling.children + return 0 + + def gencode(self, file, pass_num): + """Generate static initalizer code for this part. Two passes + are used - the first generates type information, and the second + generates instance information""" + if (pass_num == 0): + if (self.chip_or_device == 'chip'): + return; + else: + if (self.instance): + file.write("struct device %s;\n" \ + % self.instance_name) + else: + file.write("struct device dev_root;\n") + return + # This is pass the second, which is pass number 1 + # this is really just a case statement ... + + if (self.chip_or_device == 'chip'): + if (self.chipconfig): + debug.info(debug.gencode, "gencode: chipconfig(%d)" % \ + self.instance) + file.write("struct %s_config %s" % (self.type_name ,\ + self.chipinfo_name)) + if (self.registercode): + file.write("\t= {\n") + for f, v in self.registercode.items(): + file.write( "\t.%s = %s,\n" % (f, v)) + file.write("};\n") + else: + file.write(";") + file.write("\n") + + if (self.instance == 0): + self.instance_name = "dev_root" + file.write("struct device **last_dev_p = &%s.next;\n" % (self.image.last_device.instance_name)) + file.write("struct device dev_root = {\n") + file.write("\t.ops = &default_dev_ops_root,\n") + file.write("\t.bus = &dev_root.link[0],\n") + file.write("\t.path = { .type = DEVICE_PATH_ROOT },\n") + file.write("\t.enabled = 1,\n\t.links = 1,\n") + file.write("\t.on_mainboard = 1,\n") + file.write("\t.link = {\n\t\t[0] = {\n") + file.write("\t\t\t.dev=&dev_root,\n\t\t\t.link = 0,\n") + file.write("\t\t\t.children = &%s,\n" % self.firstchilddevice().instance_name) + file.write("\t\t},\n") + file.write("\t},\n") + if (self.chipconfig): + file.write("\t.chip_ops = &%s_ops,\n" % self.type_name) + file.write("\t.chip_info = &%s_info_%s,\n" % (self.type_name, self.instance)) + file.write("\t.next = &%s,\n" % self.firstchilddevice().instance_name) + file.write("};\n") + return + + # Don't print duplicate devices, just print their children + if (self.dup): + return + + file.write("struct device %s = {\n" % self.instance_name) + file.write("\t.ops = 0,\n") + file.write("\t.bus = &%s.link[%d],\n" % \ + (self.firstparentdevice().instance_name, \ + self.firstparentdevicelink())) + file.write("\t.path = {%s},\n" % self.path) + file.write("\t.enabled = %d,\n" % self.enabled) + file.write("\t.on_mainboard = 1,\n") + if (self.resources): + file.write("\t.resources = %d,\n" % self.resources) + file.write("\t.resource = {%s\n\t },\n" % self.resource) + file.write("\t.link = {\n"); + links = 0 + bus = self + while(bus and (bus.path == self.path)): + child = bus.firstchilddevice() + if (child or (bus != self) or (bus.next_sibling and (bus.next_sibling.path == self.path))): + file.write("\t\t[%d] = {\n" % links) + file.write("\t\t\t.link = %d,\n" % links) + file.write("\t\t\t.dev = &%s,\n" % self.instance_name) + if (child): + file.write("\t\t\t.children = &%s,\n" %child.instance_name) + file.write("\t\t},\n") + links = links + 1 + if (1): + bus = bus.next_sibling + else: + bus = 0 + file.write("\t},\n") + file.write("\t.links = %d,\n" % (links)) + sibling = self.firstsiblingdevice(); + if (sibling): + file.write("\t.sibling = &%s,\n" % sibling.instance_name) + chip = self.firstparentchip() + if (chip and chip.chipconfig): + file.write("\t.chip_ops = &%s_ops,\n" % chip.type_name) + file.write("\t.chip_info = &%s_info_%s,\n" % (chip.type_name, chip.instance)) + if (self.next_device): + file.write("\t.next=&%s\n" % self.next_device.instance_name) + file.write("};\n") + return + + def addconfig(self, path): + """Add chip config file to this part""" + self.chipconfig = os.path.join(self.dir, path) + self.image.addconfiginclude(self.type_name, self.chipconfig) + + def addregister(self, field, value): + """Register static initialization information""" + if (self.chip_or_device != 'chip'): + fatal("Only chips can have register values") + field = dequote(field) + value = dequote(value) + setdict(self.registercode, field, value) + + def set_enabled(self, enabled): + self.enabled = enabled + + def start_resources(self): + self.resource = "" + self.resources = 0 + + def end_resources(self): + self.resource = "%s" % (self.resource) + + def add_resource(self, type, index, value): + """ Add a resource to a device """ + self.resource = "%s\n\t\t{ .flags=%s, .index=0x%x, .base=0x%x}," % (self.resource, type, index, value) + self.resources = self.resources + 1 + + def set_path(self, path): + self.path = path + if (self.prev_sibling and (self.prev_sibling.path == self.path)): + self.dup = 1 + if (self.prev_device): + self.prev_device.next_device = self.next_device + if (self.next_device): + self.next_device.prev_device = self.prev_device + if (self.image.last_device == self): + self.image.last_device = self.prev_device + self.prev_device = 0 + self.next_device = 0 + + def addpcipath(self, slot, function): + """ Add a relative pci style path from our parent to this device """ + if ((slot < 0) or (slot > 0x1f)): + fatal("Invalid device id") + if ((function < 0) or (function > 7)): + fatal("Invalid pci function %s" % function ) + self.set_path(".type=DEVICE_PATH_PCI,{.pci={ .devfn = PCI_DEVFN(0x%x,%d)}}" % (slot, function)) + + def addpnppath(self, port, device): + """ Add a relative path to a pnp device hanging off our parent """ + if ((port < 0) or (port > 65536)): + fatal("Invalid port") + if ((device < 0) or (device > 0xffff)): + fatal("Invalid device") + self.set_path(".type=DEVICE_PATH_PNP,{.pnp={ .port = 0x%x, .device = 0x%x }}" % (port, device)) + + def addi2cpath(self, device): + """ Add a relative path to a i2c device hanging off our parent """ + if ((device < 0) or (device > 0x7f)): + fatal("Invalid device") + self.set_path(".type=DEVICE_PATH_I2C,{.i2c={ .device = 0x%x }}" % (device)) + + def addapicpath(self, apic_id): + """ Add a relative path to a cpu device hanging off our parent """ + if ((apic_id < 0) or (apic_id > 255)): + fatal("Invalid device") + self.set_path(".type=DEVICE_PATH_APIC,{.apic={ .apic_id = 0x%x }}" % (apic_id)) + + def addpci_domainpath(self, pci_domain): + """ Add a pci_domain number to a chip """ + if ((pci_domain < 0) or (pci_domain > 0xffff)): + fatal("Invalid pci_domain: 0x%x is out of the range 0 to 0xffff" % pci_domain) + self.set_path(".type=DEVICE_PATH_PCI_DOMAIN,{.pci_domain={ .domain = 0x%x }}" % (pci_domain)) + + def addapic_clusterpath(self, cluster): + """ Add an apic cluster to a chip """ + if ((cluster < 0) or (cluster > 15)): + fatal("Invalid apic cluster: %d is out of the range 0 to ff" % cluster) + self.set_path(".type=DEVICE_PATH_APIC_CLUSTER,{.apic_cluster={ .cluster = 0x%x }}" % (cluster)) + + def addcpupath(self, cpu_id): + """ Add a relative path to a cpu device hanging off our parent """ + if ((cpu_id < 0) or (cpu_id > 255)): + fatal("Invalid device") + self.set_path(".type=DEVICE_PATH_CPU,{.cpu={ .id = 0x%x }}" % (cpu_id)) + + + def addcpu_buspath(self, id): + """ Add a cpu_bus to a chip """ + if ((id < 0) or (id > 255)): + fatal("Invalid device") + self.set_path(".type=DEVICE_PATH_CPU_BUS,{.cpu_bus={ .id = 0x%x }}" % (id)) + + +# ----------------------------------------------------------------------------- +# statements +# ----------------------------------------------------------------------------- + +def getdict(dict, name): + if name not in dict.keys(): + debug.info(debug.dict, "Undefined: %s" % name) + return 0 + v = dict.get(name, 0) + debug.info(debug.dict, "getdict %s returning %s" % (name, v)) + return v + +def setdict(dict, name, value): + debug.info(debug.dict, "setdict sets %s to %s" % (name, value)) + if name in dict.keys(): + print "Duplicate in dict: %s" % name + dict[name] = value + + +def addconfig(path): + global partstack + curpart = partstack.tos() + curpart.addconfig(path) + +def addregister(field, value): + global partstack + curpart = partstack.tos() + curpart.addregister(field, value) + +def devicepart(type): + global curimage, partstack + newpart = partobj(curimage, 0, partstack.tos(), type, \ + '', 0, 'device') + #print "Configuring PART %s" % (type) + partstack.push(newpart) + #print " new PART tos is now %s\n" %partstack.tos().info() + # just push TOS, so that we can pop later. + +def part(type, path, file, name): + global curimage, partstack + partdir = os.path.join(type, path) + srcdir = os.path.join(treetop, 'src') + fulldir = os.path.join(srcdir, partdir) + type_name = flatten_name(partdir) + #print "PART(%s, %s, %s, %s)\n" % (type, path, file, name) + newpart = partobj(curimage, fulldir, partstack.tos(), type, \ + type_name, name, 'chip') + #print "Configuring PART %s, path %s" % (type, path) + partstack.push(newpart) + +def partpop(): + global partstack + curpart = partstack.tos() + if (curpart == 0): + fatal("Trying to pop non-existent part") + #print "End PART %s" % curpart.part + oldpart = partstack.pop() + #print "partstack.pop, TOS is now %s\n" % oldpart.info() + +#============================================================================= +# MISC FUNCTIONS +#============================================================================= +def dequote(str): + a = re.sub("^\"", "", str) + a = re.sub("\"$", "", a) + # highly un-intuitive, need four \! + a = re.sub("\\\\\"", "\"", a) + return a + +def flatten_name(str): + a = re.sub("[/-]", "_", str) + return a +%% +parser Config: + ignore: r'\s+' + ignore: "#.*?\r?\n" + + # less general tokens should come first, otherwise they get matched + # by the re's + token COMMENT: 'comment' + token CPU: 'cpu' + token CPU_BUS: 'cpu_bus' + token CHIP: 'chip' + token DEVICE: 'device' + token DEVICE_ID: 'device_id' + token DRQ: 'drq' + token END: 'end' + token EOF: '$' + token EQ: '=' + token FORMAT: 'format' + token IO: 'io' + token IRQ: 'irq' + token MEM: 'mem' + token NEVER: 'never' + token NONE: 'none' + token PMC: 'pmc' + token PRINT: 'print' + token REGISTER: 'register' + token VENDOR_ID: 'vendor_id' + token WRITE: 'write' + token NUM: '[0-9]+' + token HEX_NUM: '[0-9a-fA-F]+' + token HEX_PREFIX: '0x' + # Why is path separate? Because paths to resources have to at least + # have a slash, we thinks + token PATH: r'[-a-zA-Z0-9_.][-a-zA-Z0-9/_.]+[-a-zA-Z0-9_.]+' + # Dir's on the other hand are abitrary + # this may all be stupid. + token RULE: r'[-a-zA-Z0-9_$()./]+[-a-zA-Z0-9_ $()./]+[-a-zA-Z0-9_$()./]+' + token ID: r'[a-zA-Z_.]+[a-zA-Z0-9_.]*' + token STR: r'"([^\\"]+|\\.)*"' + token RAWTEXT: r'.*' + token ON: 'on' + token OFF: 'off' + token PCI: 'pci' + token PNP: 'pnp' + token I2C: 'i2c' + token APIC: 'apic' + token APIC_CLUSTER: 'apic_cluster' + token CPU: 'cpu' + token CPU_BUS: 'cpu_bus' + token PCI_DOMAIN: 'pci_domain' + + + rule expr: logical {{ l = logical }} + ( "&&" logical {{ l = l and logical }} + | "[|][|]" logical {{ l = l or logical }} + )* {{ return l }} + + rule logical: factor {{ n = factor }} + ( "[+]" factor {{ n = n+factor }} + | "-" factor {{ n = n-factor }} + )* {{ return n }} + + rule factor: term {{ v = term }} + ( "[*]" term {{ v = v*term }} + | "/" term {{ v = v/term }} + | "<<" term {{ v = v << term }} + | ">=" term {{ v = (v < term)}} + )* {{ return v }} + + # A term is a number, variable, or an expression surrounded by parentheses + rule term: NUM {{ return long(NUM, 10) }} + | HEX_PREFIX HEX_NUM {{ return long(HEX_NUM, 16) }} + | ID {{ return lookup(ID) }} + | unop {{ return unop }} + | "\\(" expr "\\)" {{ return expr }} + + rule unop: "!" expr {{ return not(expr) }} + + rule partend<>: (stmt<>)* END {{ if (C): partpop()}} + + # This is needed because the legacy cpu command could not distinguish + # between cpu vendors. It should just be PATH, but getting this change + # into the source tree will be tricky... + # DO NOT USE ID AS IT MAY GO AWAY IN THE FUTURE + rule partid: ID {{ return ID }} + | PATH {{ return PATH }} + + rule parttype: CHIP {{ return '' }} + + rule partdef<>: {{ name = 0 }} + parttype partid + [ STR {{ name = dequote(STR) }} + ] {{ if (C): part(parttype, partid, 'Config.lb', name) }} + partend<> + + rule field: STR {{ return STR }} + + rule register<>: REGISTER field '=' STR {{ if (C): addregister(field, STR) }} + + rule enable<>: {{ val = 1 }} + ( ON {{ val = 1 }} + | OFF {{ val = 0 }} + ) {{ if(C): partstack.tos().set_enabled(val) }} + + rule resource<>: {{ type = "" }} + ( IO {{ type = "IORESOURCE_FIXED | IORESOURCE_ASSIGNED | IORESOURCE_IO" }} + | MEM {{ type = "IORESOURCE_FIXED | IORESOURCE_ASSIGNED | IORESOURCE_MEM" }} + | IRQ {{ type = "IORESOURCE_FIXED | IORESOURCE_ASSIGNED | IORESOURCE_IRQ" }} + | DRQ {{ type = "IORESOURCE_FIXED | IORESOURCE_ASSIGNED | IORESOURCE_DRQ" }} + ) + term '=' {{ index = term }} + term {{ value = term }} + {{ if (C): partstack.tos().add_resource(type, index, value) }} + + + rule resources<>: {{ if (C): partstack.tos().start_resources() }} + ( resource<> )* + {{ if (C): partstack.tos().end_resources() }} + + + rule pci<>: PCI {{ if (C): devicepart('pci') }} + + HEX_NUM {{ slot = int(HEX_NUM,16) }} + '.' HEX_NUM {{ function = int(HEX_NUM, 16) }} + {{ if (C): partstack.tos().addpcipath(slot, function) }} + rule pci_domain<>: + PCI_DOMAIN {{ if (C): devicepart('pci_domain') }} + HEX_NUM {{ pci_domain = int(HEX_NUM, 16) }} + {{ if (C): partstack.tos().addpci_domainpath(pci_domain) }} + + rule pnp<>: PNP {{ if (C): devicepart('pnp') }} + HEX_NUM {{ port = int(HEX_NUM,16) }} + '.' HEX_NUM {{ device = int(HEX_NUM, 16) }} + {{ if (C): partstack.tos().addpnppath(port, device) }} + + rule i2c<>: I2C {{ if (C): devicepart('i2c') }} + HEX_NUM {{ device = int(HEX_NUM, 16) }} + {{ if (C): partstack.tos().addi2cpath(device) }} + + rule apic<>: APIC {{ if (C): devicepart('apic') }} + HEX_NUM {{ apic_id = int(HEX_NUM, 16) }} + {{ if (C): partstack.tos().addapicpath(apic_id) }} + + rule apic_cluster<>: APIC_CLUSTER {{ if (C): devicepart('apic_cluster') }} + HEX_NUM {{ cluster = int(HEX_NUM, 16) }} + {{ if (C): partstack.tos().addapic_clusterpath(cluster) }} + + rule cpu<>: CPU {{ if (C): devicepart('cpu') }} + HEX_NUM {{ id = int(HEX_NUM, 16) }} + {{ if (C): partstack.tos().addcpupath(id) }} + + rule cpu_bus<>: CPU_BUS {{ if (C): devicepart('cpu_bus') }} + HEX_NUM {{ id = int(HEX_NUM, 16) }} + {{ if (C): partstack.tos().addcpu_buspath(id) }} + + rule dev_path<>: + pci<> {{ return pci }} + | pci_domain<> {{ return pci_domain }} + | pnp<> {{ return pnp }} + | i2c<> {{ return i2c }} + | apic<> {{ return apic }} + | apic_cluster<> {{ return apic_cluster }} + | cpu<> {{ return cpu }} + | cpu_bus<> {{ return cpu_bus }} + + rule prtval: expr {{ return str(expr) }} + | STR {{ return STR }} + + rule prtlist: prtval {{ el = "%(" + prtval }} + ( "," prtval {{ el = el + "," + prtval }} + )* {{ return el + ")" }} + + rule prtstmt<>: PRINT STR {{ val = STR }} + [ "," prtlist {{ val = val + prtlist }} + ] {{ if (C): print eval(val) }} + + rule device<>: DEVICE dev_path<> + enable<> + resources<> + partend<> + + rule stmt<>: + partdef<> {{ return partdef }} + | prtstmt<> {{ return prtstmt }} + | register<> {{ return register }} + | device<> {{ return device }} + + rule value: STR {{ return dequote(STR) }} + | expr {{ return expr }} + + rule devicetree: partdef<<1>> + EOF {{ return 1 }} + + rule wrstr<>: STR {{ setwrite(ID, dequote(STR)) }} + +%% + +#============================================================================= +# FILE OUTPUT +#============================================================================= + +def dumptree(part, lvl): + debug.info(debug.dumptree, "DUMPTREE ME is") + print "%s " % part + part.dumpme(lvl) + # dump the siblings -- actually are there any? not sure + # siblings are: + debug.info(debug.dumptree, "DUMPTREE SIBLINGS are") + kid = part.next_sibling + while (kid): + kid.dumpme(lvl) + kid = kid.next_sibling + # dump the kids + debug.info(debug.dumptree, "DUMPTREE KIDS are") + #for kid in part.children: + if (part.children): + dumptree(part.children, lvl+1) + kid = part.next_sibling + while (kid): + if (kid.children): + dumptree(kid.children, lvl + 1) + kid = kid.next_sibling + debug.info(debug.dumptree, "DONE DUMPTREE") + +def writecode(image): + filename = os.path.join(img_dir, "static.c") + print "Creating", filename + file = safe_open(filename, 'w+') + file.write("#include \n") + file.write("#include \n") + for path in image.getconfigincludes().values(): + file.write("#include \"%s\"\n" % path) + file.write("\n/* pass 0 */\n") + gencode(image.getroot(), file, 0) + file.write("\n/* pass 1 */\n") + gencode(image.getroot(), file, 1) + file.close() + +def gencode(part, file, pass_num): + debug.info(debug.gencode, "GENCODE ME is") + part.gencode(file, pass_num) + # dump the siblings -- actually are there any? not sure + debug.info(debug.gencode, "GENCODE SIBLINGS are") + kid = part.next_sibling + while (kid): + kid.gencode(file, pass_num) + kid = kid.next_sibling + # now dump the children + debug.info(debug.gencode, "GENCODE KIDS are") + if (part.children): + gencode(part.children, file, pass_num) + kid = part.next_sibling + while (kid): + if (kid.children): + gencode(kid.children, file, pass_num) + kid = kid.next_sibling + debug.info(debug.gencode, "DONE GENCODE") + +def writegraph(image): + filename = os.path.join(img_dir, "static.dot") + print "Creating", filename + file = safe_open(filename, 'w+') + file.write("digraph devicetree {\n") + file.write(" rankdir=LR\n") + genranks(image.getroot(), file, 0) + gennodes(image.getroot(), file) + gengraph(image.getroot(), file) + file.write("}\n") + file.close() + +def genranks(part, file, level): + #file.write(" # Level %d\n" % level ) + file.write(" { rank = same; \"dev_%s_%d\"" % (part.type_name,part.instance )) + sib = part.next_sibling + while (sib): + file.write("; \"dev_%s_%d\"" % (sib.type_name, sib.instance)) + sib = sib.next_sibling + file.write("}\n" ) + # now dump the children + if (part.children): + genranks(part.children, file, level + 1) + + kid = part.next_sibling + while (kid): + if (kid.children): + genranks(kid.children, file, level + 1) + kid = kid.next_sibling + + +def gennodes(part, file): + file.write(" dev_%s_%d[shape=record, label=\"%s\"];\n" % (part.type_name,part.instance,part.graph_name() )) + sib = part.next_sibling + while (sib): + file.write(" dev_%s_%d[shape=record, label=\"%s\"];\n" % (sib.type_name,sib.instance,sib.graph_name() )) + sib = sib.next_sibling + # now dump the children + if (part.children): + gennodes(part.children, file) + + kid = part.next_sibling + while (kid): + if (kid.children): + gennodes(kid.children, file) + kid = kid.next_sibling + + +def gengraph(part, file): + if (part.parent != part): + file.write(" dev_%s_%d -> dev_%s_%d;\n" % \ + (part.parent.type_name, part.parent.instance, \ + part.type_name, part.instance )) + sib = part.next_sibling + while (sib): + file.write(" dev_%s_%d -> dev_%s_%d;\n" % \ + (sib.parent.type_name, sib.parent.instance, \ + sib.type_name, sib.instance )) + sib = sib.next_sibling + + kid = part.next_sibling + while (kid): + if (kid.children): + gengraph(kid.children, file) + kid = kid.next_sibling + + if (part.children): + gengraph(part.children, file) + +#============================================================================= +# MAIN PROGRAM +#============================================================================= +if __name__=='__main__': + from sys import argv + if (len(argv) < 4): + fatal("Args: ") + + file = "devicetree.cb" + partdir = os.path.join("mainboard", sys.argv[1]) + treetop = argv[2] + srcdir = os.path.join(treetop, 'src') + fulldir = os.path.join(srcdir, partdir) + type_name = flatten_name(partdir) + config_file = os.path.join(fulldir, file) + + curimage = romimage("new") + image = curimage + + newpart = partobj(curimage, fulldir, partstack.tos(), 'mainboard', \ + 'mainboard', 0, 'chip') + #print "Configuring PART %s, path %s" % (type, path) + image.setroot(newpart); + partstack.push(newpart) + + fp = safe_open(config_file, 'r') + if (not parse('devicetree', fp.read())): + fatal("Could not parse file") + print "PARSED THE TREE" + partstack.pop() + + img_dir = argv[3] + + #debug.info(debug.dumptree, "DEVICE TREE:") + #dumptree(curimage.getroot(), 0) + + writecode(image) + writegraph(image) + + sys.exit(0) diff --git a/util/sconfig/parsedesc.g b/util/sconfig/parsedesc.g new file mode 100644 index 0000000..7113c6d --- /dev/null +++ b/util/sconfig/parsedesc.g @@ -0,0 +1,196 @@ +###################################################################### +# The remainder of this file is from parsedesc.{g,py} + +def append(lst, x): + "Imperative append" + lst.append(x) + return lst + +def add_inline_token(tokens, str): + tokens.insert( 0, (str, eval(str, {}, {})) ) + return Terminal(str) + +def cleanup_choice(lst): + if len(lst) == 0: return Sequence([]) + if len(lst) == 1: return lst[0] + return apply(Choice, tuple(lst)) + +def cleanup_sequence(lst): + if len(lst) == 1: return lst[0] + return apply(Sequence, tuple(lst)) + +def cleanup_rep(node, rep): + if rep == 'star': return Star(node) + elif rep == 'plus': return Plus(node) + else: return node + +def resolve_name(tokens, id, args): + if id in map(lambda x: x[0], tokens): + # It's a token + if args: + print 'Warning: ignoring parameters on TOKEN %s<<%s>>' % (id, args) + return Terminal(id) + else: + # It's a name, so assume it's a nonterminal + return NonTerminal(id, args) + +%% +parser ParserDescription: + option: "context-insensitive-scanner" + + ignore: "[ \t\r\n]+" + ignore: "#.*?\r?\n" + token END: "$" + token ATTR: "<<.+?>>" + token STMT: "{{.+?}}" + token ID: '[a-zA-Z_][a-zA-Z_0-9]*' + token STR: '[rR]?\'([^\\n\'\\\\]|\\\\.)*\'|[rR]?"([^\\n"\\\\]|\\\\.)*"' + token LP: '\\(' + token RP: '\\)' + token LB: '\\[' + token RB: '\\]' + token OR: '[|]' + token STAR: '[*]' + token PLUS: '[+]' + token QUEST: '[?]' + token COLON: ':' + + rule Parser: "parser" ID ":" + Options + Tokens + Rules<> + END + {{ return Generator(ID,Options,Tokens,Rules) }} + + rule Options: {{ opt = {} }} + ( "option" ":" Str {{ opt[Str] = 1 }} )* + {{ return opt }} + + rule Tokens: {{ tok = [] }} + ( + "token" ID ":" Str {{ tok.append( (ID,Str) ) }} + | "ignore" ":" Str {{ tok.append( ('#ignore',Str) ) }} + )* + {{ return tok }} + + rule Rules<>: + {{ rul = [] }} + ( + "rule" ID OptParam ":" ClauseA<> + {{ rul.append( (ID,OptParam,ClauseA) ) }} + )* + {{ return rul }} + + rule ClauseA<>: + ClauseB<> + {{ v = [ClauseB] }} + ( OR ClauseB<> {{ v.append(ClauseB) }} )* + {{ return cleanup_choice(v) }} + + rule ClauseB<>: + {{ v = [] }} + ( ClauseC<> {{ v.append(ClauseC) }} )* + {{ return cleanup_sequence(v) }} + + rule ClauseC<>: + ClauseD<> + ( PLUS {{ return Plus(ClauseD) }} + | STAR {{ return Star(ClauseD) }} + | {{ return ClauseD }} ) + + rule ClauseD<>: + STR {{ t = (STR, eval(STR,{},{})) }} + {{ if t not in tokens: tokens.insert( 0, t ) }} + {{ return Terminal(STR) }} + | ID OptParam {{ return resolve_name(tokens, ID, OptParam) }} + | LP ClauseA<> RP {{ return ClauseA }} + | LB ClauseA<> RB {{ return Option(ClauseA) }} + | STMT {{ return Eval(STMT[2:-2]) }} + + rule OptParam: [ ATTR {{ return ATTR[2:-2] }} ] {{ return '' }} + rule Str: STR {{ return eval(STR,{},{}) }} +%% + +# This replaces the default main routine + +yapps_options = [ + ('context-insensitive-scanner', 'context-insensitive-scanner', + 'Scan all tokens (see docs)') + ] + +def generate(inputfilename, outputfilename='', dump=0, **flags): + """Generate a grammar, given an input filename (X.g) + and an output filename (defaulting to X.py).""" + + if not outputfilename: + if inputfilename[-2:]=='.g': outputfilename = inputfilename[:-2]+'.py' + else: raise "Invalid Filename", outputfilename + + print 'Input Grammar:', inputfilename + print 'Output File:', outputfilename + + DIVIDER = '\n%%\n' # This pattern separates the pre/post parsers + preparser, postparser = None, None # Code before and after the parser desc + + # Read the entire file + s = open(inputfilename,'r').read() + + # See if there's a separation between the pre-parser and parser + f = find(s, DIVIDER) + if f >= 0: preparser, s = s[:f]+'\n\n', s[f+len(DIVIDER):] + + # See if there's a separation between the parser and post-parser + f = find(s, DIVIDER) + if f >= 0: s, postparser = s[:f], '\n\n'+s[f+len(DIVIDER):] + + # Create the parser and scanner + p = ParserDescription(ParserDescriptionScanner(s)) + if not p: return + + # Now parse the file + t = wrap_error_reporter(p, 'Parser') + if not t: return # Error + if preparser is not None: t.preparser = preparser + if postparser is not None: t.postparser = postparser + + # Check the options + for f in t.options.keys(): + for opt,_,_ in yapps_options: + if f == opt: break + else: + print 'Warning: unrecognized option', f + # Add command line options to the set + for f in flags.keys(): t.options[f] = flags[f] + + # Generate the output + if dump: + t.dump_information() + else: + t.output = open(outputfilename, 'w') + t.generate_output() + +if __name__=='__main__': + import sys, getopt + optlist, args = getopt.getopt(sys.argv[1:], 'f:', ['dump']) + if not args or len(args) > 2: + print 'Usage:' + print ' python', sys.argv[0], '[flags] input.g [output.py]' + print 'Flags:' + print (' --dump' + ' '*40)[:35] + 'Dump out grammar information' + for flag, _, doc in yapps_options: + print (' -f' + flag + ' '*40)[:35] + doc + else: + # Read in the options and create a list of flags + flags = {} + for opt in optlist: + for flag, name, _ in yapps_options: + if opt == ('-f', flag): + flags[name] = 1 + break + else: + if opt == ('--dump', ''): + flags['dump'] = 1 + else: + print 'Warning - unrecognized option: ', opt[0], opt[1] + + apply(generate, tuple(args), flags) diff --git a/util/sconfig/test.config b/util/sconfig/test.config new file mode 100644 index 0000000..c492f20 --- /dev/null +++ b/util/sconfig/test.config @@ -0,0 +1,6 @@ +target x +mainboard amd/solo +# option X=1 +# makerule x y "z" + payload /dev/null +end diff --git a/util/sconfig/yapps2.py b/util/sconfig/yapps2.py new file mode 100644 index 0000000..71bfa05 --- /dev/null +++ b/util/sconfig/yapps2.py @@ -0,0 +1,779 @@ +# Yapps 2.0 - yet another python parser system +# Amit J Patel, January 1999 +# See http://theory.stanford.edu/~amitp/Yapps/ for documentation and updates + +# v2.0.1 changes (October 2001): +# * The exceptions inherit the standard Exception class (thanks Rich Salz) +# * The scanner can use either a different set of regular expressions +# per instance, or allows the subclass to define class fields with +# the patterns. This improves performance when many Scanner objects +# are being created, because the regular expressions don't have to +# be recompiled each time. (thanks Amaury Forgeot d'Arc) +# v2.0.2 changes (April 2002) +# * Fixed a bug in generating the 'else' clause when the comment was too +# long. v2.0.1 was missing a newline. (thanks Steven Engelhardt) +# v2.0.3 changes (August 2002) +# * Fixed a bug with inline tokens using the r"" syntax. + +from string import * +from yappsrt import * +import re + +INDENT = " "*4 + +class Generator: + def __init__(self, name, options, tokens, rules): + self.change_count = 0 + self.name = name + self.options = options + self.preparser = '' + self.postparser = None + + self.tokens = {} # Map from tokens to regexps + self.ignore = [] # List of token names to ignore in parsing + self.terminals = [] # List of token names (to maintain ordering) + for n,t in tokens: + if n == '#ignore': + n = t + self.ignore.append(n) + if n in self.tokens.keys() and self.tokens[n] != t: + print 'Warning: token', n, 'multiply defined.' + self.tokens[n] = t + self.terminals.append(n) + + self.rules = {} # Map from rule names to parser nodes + self.params = {} # Map from rule names to parameters + self.goals = [] # List of rule names (to maintain ordering) + for n,p,r in rules: + self.params[n] = p + self.rules[n] = r + self.goals.append(n) + + import sys + self.output = sys.stdout + + def __getitem__(self, name): + # Get options + return self.options.get(name, 0) + + def non_ignored_tokens(self): + return filter(lambda x, i=self.ignore: x not in i, self.terminals) + + def changed(self): + self.change_count = 1+self.change_count + + def subset(self, a, b): + "See if all elements of a are inside b" + for x in a: + if x not in b: return 0 + return 1 + + def equal_set(self, a, b): + "See if a and b have the same elements" + if len(a) != len(b): return 0 + if a == b: return 1 + return self.subset(a, b) and self.subset(b, a) + + def add_to(self, parent, additions): + "Modify parent to include all elements in additions" + for x in additions: + if x not in parent: + parent.append(x) + self.changed() + + def equate(self, a, b): + self.add_to(a, b) + self.add_to(b, a) + + def write(self, *args): + for a in args: + self.output.write(a) + + def in_test(self, x, full, b): + if not b: return '0' + if len(b)==1: return '%s == %s' % (x, `b[0]`) + if full and len(b) > len(full)/2: + # Reverse the sense of the test. + not_b = filter(lambda x, b=b: x not in b, full) + return self.not_in_test(x, full, not_b) + return '%s in %s' % (x, `b`) + + def not_in_test(self, x, full, b): + if not b: return '1' + if len(b)==1: return '%s != %s' % (x, `b[0]`) + return '%s not in %s' % (x, `b`) + + def peek_call(self, a): + a_set = (`a`[1:-1]) + if self.equal_set(a, self.non_ignored_tokens()): a_set = '' + if self['context-insensitive-scanner']: a_set = '' + return 'self._peek(%s)' % a_set + + def peek_test(self, a, b): + if self.subset(a, b): return '1' + if self['context-insensitive-scanner']: a = self.non_ignored_tokens() + return self.in_test(self.peek_call(a), a, b) + + def not_peek_test(self, a, b): + if self.subset(a, b): return '0' + return self.not_in_test(self.peek_call(a), a, b) + + def calculate(self): + while 1: + for r in self.goals: + self.rules[r].setup(self, r) + if self.change_count == 0: break + self.change_count = 0 + + while 1: + for r in self.goals: + self.rules[r].update(self) + if self.change_count == 0: break + self.change_count = 0 + + def dump_information(self): + self.calculate() + for r in self.goals: + print ' _____' + '_'*len(r) + print ('___/Rule '+r+'\\' + '_'*80)[:79] + queue = [self.rules[r]] + while queue: + top = queue[0] + del queue[0] + + print `top` + top.first.sort() + top.follow.sort() + eps = [] + if top.accepts_epsilon: eps = ['(null)'] + print ' FIRST:', join(top.first+eps, ', ') + print ' FOLLOW:', join(top.follow, ', ') + for x in top.get_children(): queue.append(x) + + def generate_output(self): + self.calculate() + self.write(self.preparser) + self.write("from string import *\n") + self.write("import re\n") + self.write("from yappsrt import *\n") + self.write("\n") + self.write("class ", self.name, "Scanner(Scanner):\n") + self.write(" patterns = [\n") + for p in self.terminals: + self.write(" (%s, re.compile(%s)),\n" % ( + `p`, `self.tokens[p]`)) + self.write(" ]\n") + self.write(" def __init__(self, str):\n") + self.write(" Scanner.__init__(self,None,%s,str)\n" % + `self.ignore`) + self.write("\n") + + self.write("class ", self.name, "(Parser):\n") + for r in self.goals: + self.write(INDENT, "def ", r, "(self") + if self.params[r]: self.write(", ", self.params[r]) + self.write("):\n") + self.rules[r].output(self, INDENT+INDENT) + self.write("\n") + + self.write("\n") + self.write("def parse(rule, text):\n") + self.write(" P = ", self.name, "(", self.name, "Scanner(text))\n") + self.write(" return wrap_error_reporter(P, rule)\n") + self.write("\n") + if self.postparser is not None: + self.write(self.postparser) + else: + self.write("if __name__=='__main__':\n") + self.write(INDENT, "from sys import argv, stdin\n") + self.write(INDENT, "if len(argv) >= 2:\n") + self.write(INDENT*2, "if len(argv) >= 3:\n") + self.write(INDENT*3, "f = open(argv[2],'r')\n") + self.write(INDENT*2, "else:\n") + self.write(INDENT*3, "f = stdin\n") + self.write(INDENT*2, "print parse(argv[1], f.read())\n") + self.write(INDENT, "else: print 'Args: []'\n") + +###################################################################### +class Node: + def __init__(self): + self.first = [] + self.follow = [] + self.accepts_epsilon = 0 + self.rule = '?' + + def setup(self, gen, rule): + # Setup will change accepts_epsilon, + # sometimes from 0 to 1 but never 1 to 0. + # It will take a finite number of steps to set things up + self.rule = rule + + def used(self, vars): + "Return two lists: one of vars used, and the other of vars assigned" + return vars, [] + + def get_children(self): + "Return a list of sub-nodes" + return [] + + def __repr__(self): + return str(self) + + def update(self, gen): + if self.accepts_epsilon: + gen.add_to(self.first, self.follow) + + def output(self, gen, indent): + "Write out code to _gen_ with _indent_:string indentation" + gen.write(indent, "assert 0 # Invalid parser node\n") + +class Terminal(Node): + def __init__(self, token): + Node.__init__(self) + self.token = token + self.accepts_epsilon = 0 + + def __str__(self): + return self.token + + def update(self, gen): + Node.update(self, gen) + if self.first != [self.token]: + self.first = [self.token] + gen.changed() + + def output(self, gen, indent): + gen.write(indent) + if re.match('[a-zA-Z_]+$', self.token): + gen.write(self.token, " = ") + gen.write("self._scan(%s)\n" % `self.token`) + +class Eval(Node): + def __init__(self, expr): + Node.__init__(self) + self.expr = expr + + def setup(self, gen, rule): + Node.setup(self, gen, rule) + if not self.accepts_epsilon: + self.accepts_epsilon = 1 + gen.changed() + + def __str__(self): + return '{{ %s }}' % strip(self.expr) + + def output(self, gen, indent): + gen.write(indent, strip(self.expr), '\n') + +class NonTerminal(Node): + def __init__(self, name, args): + Node.__init__(self) + self.name = name + self.args = args + + def setup(self, gen, rule): + Node.setup(self, gen, rule) + try: + self.target = gen.rules[self.name] + if self.accepts_epsilon != self.target.accepts_epsilon: + self.accepts_epsilon = self.target.accepts_epsilon + gen.changed() + except KeyError: # Oops, it's nonexistent + print 'Error: no rule <%s>' % self.name + self.target = self + + def __str__(self): + return '<%s>' % self.name + + def update(self, gen): + Node.update(self, gen) + gen.equate(self.first, self.target.first) + gen.equate(self.follow, self.target.follow) + + def output(self, gen, indent): + gen.write(indent) + gen.write(self.name, " = ") + gen.write("self.", self.name, "(", self.args, ")\n") + +class Sequence(Node): + def __init__(self, *children): + Node.__init__(self) + self.children = children + + def setup(self, gen, rule): + Node.setup(self, gen, rule) + for c in self.children: c.setup(gen, rule) + + if not self.accepts_epsilon: + # If it's not already accepting epsilon, it might now do so. + for c in self.children: + # any non-epsilon means all is non-epsilon + if not c.accepts_epsilon: break + else: + self.accepts_epsilon = 1 + gen.changed() + + def get_children(self): + return self.children + + def __str__(self): + return '( %s )' % join(map(lambda x: str(x), self.children)) + + def update(self, gen): + Node.update(self, gen) + for g in self.children: + g.update(gen) + + empty = 1 + for g_i in range(len(self.children)): + g = self.children[g_i] + + if empty: gen.add_to(self.first, g.first) + if not g.accepts_epsilon: empty = 0 + + if g_i == len(self.children)-1: + next = self.follow + else: + next = self.children[1+g_i].first + gen.add_to(g.follow, next) + + if self.children: + gen.add_to(self.follow, self.children[-1].follow) + + def output(self, gen, indent): + if self.children: + for c in self.children: + c.output(gen, indent) + else: + # Placeholder for empty sequences, just in case + gen.write(indent, 'pass\n') + +class Choice(Node): + def __init__(self, *children): + Node.__init__(self) + self.children = children + + def setup(self, gen, rule): + Node.setup(self, gen, rule) + for c in self.children: c.setup(gen, rule) + + if not self.accepts_epsilon: + for c in self.children: + if c.accepts_epsilon: + self.accepts_epsilon = 1 + gen.changed() + + def get_children(self): + return self.children + + def __str__(self): + return '( %s )' % join(map(lambda x: str(x), self.children), ' | ') + + def update(self, gen): + Node.update(self, gen) + for g in self.children: + g.update(gen) + + for g in self.children: + gen.add_to(self.first, g.first) + gen.add_to(self.follow, g.follow) + for g in self.children: + gen.add_to(g.follow, self.follow) + if self.accepts_epsilon: + gen.add_to(self.first, self.follow) + + def output(self, gen, indent): + test = "if" + gen.write(indent, "_token_ = ", gen.peek_call(self.first), "\n") + tokens_seen = [] + tokens_unseen = self.first[:] + if gen['context-insensitive-scanner']: + # Context insensitive scanners can return ANY token, + # not only the ones in first. + tokens_unseen = gen.non_ignored_tokens() + for c in self.children: + testset = c.first[:] + removed = [] + for x in testset: + if x in tokens_seen: + testset.remove(x) + removed.append(x) + if x in tokens_unseen: tokens_unseen.remove(x) + tokens_seen = tokens_seen + testset + if removed: + if not testset: + print 'Error in rule', self.rule+':', c, 'never matches.' + else: + print 'Warning:', self + print ' * These tokens are being ignored:', join(removed, ', ') + print ' due to previous choices using them.' + + if testset: + if not tokens_unseen: # context sensitive scanners only! + if test=='if': + # if it's the first AND last test, then + # we can simply put the code without an if/else + c.output(gen, indent) + else: + gen.write(indent, "else: ") + t = gen.in_test('', [], testset) + if len(t) < 70-len(indent): + gen.write("#", t) + gen.write("\n") + c.output(gen, indent+INDENT) + else: + gen.write(indent, test, " ", + gen.in_test('_token_', tokens_unseen, testset), + ":\n") + c.output(gen, indent+INDENT) + test = "elif" + + if gen['context-insensitive-scanner'] and tokens_unseen: + gen.write(indent, "else:\n") + gen.write(indent, INDENT, "raise SyntaxError(self._pos, ") + gen.write("'Could not match ", self.rule, "')\n") + +class Wrapper(Node): + def __init__(self, child): + Node.__init__(self) + self.child = child + + def setup(self, gen, rule): + Node.setup(self, gen, rule) + self.child.setup(gen, rule) + + def get_children(self): + return [self.child] + + def update(self, gen): + Node.update(self, gen) + self.child.update(gen) + gen.add_to(self.first, self.child.first) + gen.equate(self.follow, self.child.follow) + +class Option(Wrapper): + def setup(self, gen, rule): + Wrapper.setup(self, gen, rule) + if not self.accepts_epsilon: + self.accepts_epsilon = 1 + gen.changed() + + def __str__(self): + return '[ %s ]' % str(self.child) + + def output(self, gen, indent): + if self.child.accepts_epsilon: + print 'Warning in rule', self.rule+': contents may be empty.' + gen.write(indent, "if %s:\n" % + gen.peek_test(self.first, self.child.first)) + self.child.output(gen, indent+INDENT) + +class Plus(Wrapper): + def setup(self, gen, rule): + Wrapper.setup(self, gen, rule) + if self.accepts_epsilon != self.child.accepts_epsilon: + self.accepts_epsilon = self.child.accepts_epsilon + gen.changed() + + def __str__(self): + return '%s+' % str(self.child) + + def update(self, gen): + Wrapper.update(self, gen) + gen.add_to(self.follow, self.first) + + def output(self, gen, indent): + if self.child.accepts_epsilon: + print 'Warning in rule', self.rule+':' + print ' * The repeated pattern could be empty. The resulting' + print ' parser may not work properly.' + gen.write(indent, "while 1:\n") + self.child.output(gen, indent+INDENT) + union = self.first[:] + gen.add_to(union, self.follow) + gen.write(indent+INDENT, "if %s: break\n" % + gen.not_peek_test(union, self.child.first)) + +class Star(Plus): + def setup(self, gen, rule): + Wrapper.setup(self, gen, rule) + if not self.accepts_epsilon: + self.accepts_epsilon = 1 + gen.changed() + + def __str__(self): + return '%s*' % str(self.child) + + def output(self, gen, indent): + if self.child.accepts_epsilon: + print 'Warning in rule', self.rule+':' + print ' * The repeated pattern could be empty. The resulting' + print ' parser probably will not work properly.' + gen.write(indent, "while %s:\n" % + gen.peek_test(self.follow, self.child.first)) + self.child.output(gen, indent+INDENT) + +###################################################################### +# The remainder of this file is from parsedesc.{g,py} + +def append(lst, x): + "Imperative append" + lst.append(x) + return lst + +def add_inline_token(tokens, str): + tokens.insert( 0, (str, eval(str, {}, {})) ) + return Terminal(str) + +def cleanup_choice(lst): + if len(lst) == 0: return Sequence([]) + if len(lst) == 1: return lst[0] + return apply(Choice, tuple(lst)) + +def cleanup_sequence(lst): + if len(lst) == 1: return lst[0] + return apply(Sequence, tuple(lst)) + +def cleanup_rep(node, rep): + if rep == 'star': return Star(node) + elif rep == 'plus': return Plus(node) + else: return node + +def resolve_name(tokens, id, args): + if id in map(lambda x: x[0], tokens): + # It's a token + if args: + print 'Warning: ignoring parameters on TOKEN %s<<%s>>' % (id, args) + return Terminal(id) + else: + # It's a name, so assume it's a nonterminal + return NonTerminal(id, args) + + +from string import * +import re +from yappsrt import * + +class ParserDescriptionScanner(Scanner): + def __init__(self, str): + Scanner.__init__(self,[ + ('"rule"', 'rule'), + ('"ignore"', 'ignore'), + ('"token"', 'token'), + ('"option"', 'option'), + ('":"', ':'), + ('"parser"', 'parser'), + ('[ \011\015\012]+', '[ \011\015\012]+'), + ('#.*?\015?\012', '#.*?\015?\012'), + ('END', '$'), + ('ATTR', '<<.+?>>'), + ('STMT', '{{.+?}}'), + ('ID', '[a-zA-Z_][a-zA-Z_0-9]*'), + ('STR', '[rR]?\'([^\\n\'\\\\]|\\\\.)*\'|[rR]?"([^\\n"\\\\]|\\\\.)*"'), + ('LP', '\\('), + ('RP', '\\)'), + ('LB', '\\['), + ('RB', '\\]'), + ('OR', '[|]'), + ('STAR', '[*]'), + ('PLUS', '[+]'), + ], ['[ \011\015\012]+', '#.*?\015?\012'], str) + +class ParserDescription(Parser): + def Parser(self): + self._scan('"parser"') + ID = self._scan('ID') + self._scan('":"') + Options = self.Options() + Tokens = self.Tokens() + Rules = self.Rules(Tokens) + END = self._scan('END') + return Generator(ID,Options,Tokens,Rules) + + def Options(self): + opt = {} + while self._peek('"option"', '"token"', '"ignore"', 'END', '"rule"') == '"option"': + self._scan('"option"') + self._scan('":"') + Str = self.Str() + opt[Str] = 1 + return opt + + def Tokens(self): + tok = [] + while self._peek('"token"', '"ignore"', 'END', '"rule"') in ['"token"', '"ignore"']: + _token_ = self._peek('"token"', '"ignore"') + if _token_ == '"token"': + self._scan('"token"') + ID = self._scan('ID') + self._scan('":"') + Str = self.Str() + tok.append( (ID,Str) ) + else: # == '"ignore"' + self._scan('"ignore"') + self._scan('":"') + Str = self.Str() + tok.append( ('#ignore',Str) ) + return tok + + def Rules(self, tokens): + rul = [] + while self._peek('"rule"', 'END') == '"rule"': + self._scan('"rule"') + ID = self._scan('ID') + OptParam = self.OptParam() + self._scan('":"') + ClauseA = self.ClauseA(tokens) + rul.append( (ID,OptParam,ClauseA) ) + return rul + + def ClauseA(self, tokens): + ClauseB = self.ClauseB(tokens) + v = [ClauseB] + while self._peek('OR', 'RP', 'RB', '"rule"', 'END') == 'OR': + OR = self._scan('OR') + ClauseB = self.ClauseB(tokens) + v.append(ClauseB) + return cleanup_choice(v) + + def ClauseB(self, tokens): + v = [] + while self._peek('STR', 'ID', 'LP', 'LB', 'STMT', 'OR', 'RP', 'RB', '"rule"', 'END') in ['STR', 'ID', 'LP', 'LB', 'STMT']: + ClauseC = self.ClauseC(tokens) + v.append(ClauseC) + return cleanup_sequence(v) + + def ClauseC(self, tokens): + ClauseD = self.ClauseD(tokens) + _token_ = self._peek('PLUS', 'STAR', 'STR', 'ID', 'LP', 'LB', 'STMT', 'OR', 'RP', 'RB', '"rule"', 'END') + if _token_ == 'PLUS': + PLUS = self._scan('PLUS') + return Plus(ClauseD) + elif _token_ == 'STAR': + STAR = self._scan('STAR') + return Star(ClauseD) + else: + return ClauseD + + def ClauseD(self, tokens): + _token_ = self._peek('STR', 'ID', 'LP', 'LB', 'STMT') + if _token_ == 'STR': + STR = self._scan('STR') + t = (STR, eval(STR,{},{})) + if t not in tokens: tokens.insert( 0, t ) + return Terminal(STR) + elif _token_ == 'ID': + ID = self._scan('ID') + OptParam = self.OptParam() + return resolve_name(tokens, ID, OptParam) + elif _token_ == 'LP': + LP = self._scan('LP') + ClauseA = self.ClauseA(tokens) + RP = self._scan('RP') + return ClauseA + elif _token_ == 'LB': + LB = self._scan('LB') + ClauseA = self.ClauseA(tokens) + RB = self._scan('RB') + return Option(ClauseA) + else: # == 'STMT' + STMT = self._scan('STMT') + return Eval(STMT[2:-2]) + + def OptParam(self): + if self._peek('ATTR', '":"', 'PLUS', 'STAR', 'STR', 'ID', 'LP', 'LB', 'STMT', 'OR', 'RP', 'RB', '"rule"', 'END') == 'ATTR': + ATTR = self._scan('ATTR') + return ATTR[2:-2] + return '' + + def Str(self): + STR = self._scan('STR') + return eval(STR,{},{}) + + + + + +# This replaces the default main routine + +yapps_options = [ + ('context-insensitive-scanner', 'context-insensitive-scanner', + 'Scan all tokens (see docs)') + ] + +def generate(inputfilename, outputfilename='', dump=0, **flags): + """Generate a grammar, given an input filename (X.g) + and an output filename (defaulting to X.py).""" + + if not outputfilename: + if inputfilename[-2:]=='.g': outputfilename = inputfilename[:-2]+'.py' + else: raise "Invalid Filename", outputfilename + + print 'Input Grammar:', inputfilename + print 'Output File:', outputfilename + + DIVIDER = '\n%%\n' # This pattern separates the pre/post parsers + preparser, postparser = None, None # Code before and after the parser desc + + # Read the entire file + s = open(inputfilename,'r').read() + + # See if there's a separation between the pre-parser and parser + f = find(s, DIVIDER) + if f >= 0: preparser, s = s[:f]+'\n\n', s[f+len(DIVIDER):] + + # See if there's a separation between the parser and post-parser + f = find(s, DIVIDER) + if f >= 0: s, postparser = s[:f], '\n\n'+s[f+len(DIVIDER):] + + # Create the parser and scanner + p = ParserDescription(ParserDescriptionScanner(s)) + if not p: return + + # Now parse the file + t = wrap_error_reporter(p, 'Parser') + if not t: return # Error + if preparser is not None: t.preparser = preparser + if postparser is not None: t.postparser = postparser + + # Check the options + for f in t.options.keys(): + for opt,_,_ in yapps_options: + if f == opt: break + else: + print 'Warning: unrecognized option', f + # Add command line options to the set + for f in flags.keys(): t.options[f] = flags[f] + + # Generate the output + if dump: + t.dump_information() + else: + t.output = open(outputfilename, 'w') + t.generate_output() + +if __name__=='__main__': + import sys, getopt + optlist, args = getopt.getopt(sys.argv[1:], 'f:', ['dump']) + if not args or len(args) > 2: + print 'Usage:' + print ' python', sys.argv[0], '[flags] input.g [output.py]' + print 'Flags:' + print (' --dump' + ' '*40)[:35] + 'Dump out grammar information' + for flag, _, doc in yapps_options: + print (' -f' + flag + ' '*40)[:35] + doc + else: + # Read in the options and create a list of flags + flags = {} + for opt in optlist: + for flag, name, _ in yapps_options: + if opt == ('-f', flag): + flags[name] = 1 + break + else: + if opt == ('--dump', ''): + flags['dump'] = 1 + else: + print 'Warning - unrecognized option: ', opt[0], opt[1] + + apply(generate, tuple(args), flags) diff --git a/util/sconfig/yapps2.tex b/util/sconfig/yapps2.tex new file mode 100644 index 0000000..9d2bddf --- /dev/null +++ b/util/sconfig/yapps2.tex @@ -0,0 +1,1225 @@ +\documentclass[10pt]{article} +\usepackage{palatino} +\usepackage{html} +\usepackage{color} + +\setlength{\headsep}{0in} +\setlength{\headheight}{0in} +\setlength{\textheight}{8.5in} +\setlength{\textwidth}{5.9in} +\setlength{\oddsidemargin}{0.25in} + +\definecolor{darkblue}{rgb}{0,0,0.6} +\definecolor{darkerblue}{rgb}{0,0,0.3} + +%% \newcommand{\mysection}[1]{\section{\textcolor{darkblue}{#1}}} +%% \newcommand{\mysubsection}[1]{\subsection{\textcolor{darkerblue}{#1}}} +\newcommand{\mysection}[1]{\section{#1}} +\newcommand{\mysubsection}[1]{\subsection{#1}} + +\bodytext{bgcolor=white text=black link=#004080 vlink=#006020} + +\newcommand{\first}{\textsc{first}} +\newcommand{\follow}{\textsc{follow}} + +\begin{document} + +\begin{center} +\hfill \begin{tabular}{c} +{\Large The \emph{Yapps} Parser Generator System}\\ +\verb|http://theory.stanford.edu/~amitp/Yapps/|\\ + Version 2\\ +\\ +Amit J. Patel\\ +\htmladdnormallink{http://www-cs-students.stanford.edu/~amitp/} +{http://www-cs-students.stanford.edu/~amitp/} + +\end{tabular} \hfill \rule{0in}{0in} +\end{center} + +\mysection{Introduction} + +\emph{Yapps} (\underline{Y}et \underline{A}nother \underline{P}ython +\underline{P}arser \underline{S}ystem) is an easy to use parser +generator that is written in Python and generates Python code. There +are several parser generator systems already available for Python, +including \texttt{PyLR, kjParsing, PyBison,} and \texttt{mcf.pars,} +but I had different goals for my parser. Yapps is simple, is easy to +use, and produces human-readable parsers. It is not the fastest or +most powerful parser. Yapps is designed to be used when regular +expressions are not enough and other parser systems are too much: +situations where you may write your own recursive descent parser. + +Some unusual features of Yapps that may be of interest are: + +\begin{enumerate} + + \item Yapps produces recursive descent parsers that are readable by + humans, as opposed to table-driven parsers that are difficult to + read. A Yapps parser for a simple calculator looks similar to the + one that Mark Lutz wrote by hand for \emph{Programming Python.} + + \item Yapps also allows for rules that accept parameters and pass + arguments to be used while parsing subexpressions. Grammars that + allow for arguments to be passed to subrules and for values to be + passed back are often called \emph{attribute grammars.} In many + cases parameterized rules can be used to perform actions at ``parse + time'' that are usually delayed until later. For example, + information about variable declarations can be passed into the + rules that parse a procedure body, so that undefined variables can + be detected at parse time. The types of defined variables can be + used in parsing as well---for example, if the type of {\tt X} is + known, we can determine whether {\tt X(1)} is an array reference or + a function call. + + \item Yapps grammars are fairly easy to write, although there are + some inconveniences having to do with ELL(1) parsing that have to be + worked around. For example, rules have to be left factored and + rules may not be left recursive. However, neither limitation seems + to be a problem in practice. + + Yapps grammars look similar to the notation used in the Python + reference manual, with operators like \verb:*:, \verb:+:, \verb:|:, + \verb:[]:, and \verb:(): for patterns, names ({\tt tim}) for rules, + regular expressions (\verb:"[a-z]+":) for tokens, and \verb:#: for + comments. + + \item The Yapps parser generator is written as a single Python module + with no C extensions. Yapps produces parsers that are written + entirely in Python, and require only the Yapps run-time module (5k) + for support. + + \item Yapps's scanner is context-sensitive, picking tokens based on + the types of the tokens accepted by the parser. This can be + helpful when implementing certain kinds of parsers, such as for a + preprocessor. + +\end{enumerate} + +There are several disadvantages of using Yapps over another parser system: + +\begin{enumerate} + + \item Yapps parsers are \texttt{ELL(1)} (Extended LL(1)), which is + less powerful than \texttt{LALR} (used by \texttt{PyLR}) or + \texttt{SLR} (used by \texttt{kjParsing}), so Yapps would not be a + good choice for parsing complex languages. For example, allowing + both \texttt{x := 5;} and \texttt{x;} as statements is difficult + because we must distinguish based on only one token of lookahead. + Seeing only \texttt{x}, we cannot decide whether we have an + assignment statement or an expression statement. (Note however + that this kind of grammar can be matched with backtracking; see + section \ref{sec:future}.) + + \item The scanner that Yapps provides can only read from strings, not + files, so an entire file has to be read in before scanning can + begin. It is possible to build a custom scanner, though, so in + cases where stream input is needed (from the console, a network, or + a large file are examples), the Yapps parser can be given a custom + scanner that reads from a stream instead of a string. + + \item Yapps is not designed with efficiency in mind. + +\end{enumerate} + +Yapps provides an easy to use parser generator that produces parsers +similar to what you might write by hand. It is not meant to be a +solution for all parsing problems, but instead an aid for those times +you would write a parser by hand rather than using one of the more +powerful parsing packages available. + +Yapps 2.0 is easier to use than Yapps 1.0. New features include a +less restrictive input syntax, which allows mixing of sequences, +choices, terminals, and nonterminals; optional matching; the ability +to insert single-line statements into the generated parser; and +looping constructs \verb|*| and \verb|+| similar to the repetitive +matching constructs in regular expressions. Unfortunately, the +addition of these constructs has made Yapps 2.0 incompatible with +Yapps 1.0, so grammars will have to be rewritten. See section +\ref{sec:Upgrading} for tips on changing Yapps 1.0 grammars for use +with Yapps 2.0. + +\mysection{Examples} + +In this section are several examples that show the use of Yapps. +First, an introduction shows how to construct grammars and write them +in Yapps form. This example can be skipped by someone familiar with +grammars and parsing. Next is a Lisp expression grammar that produces +a parse tree as output. This example demonstrates the use of tokens +and rules, as well as returning values from rules. The third example +is a expression evaluation grammar that evaluates during parsing +(instead of producing a parse tree). + +\mysubsection{Introduction to Grammars} + +A \emph{grammar} for a natural language specifies how words can be put +together to form large structures, such as phrases and sentences. A +grammar for a computer language is similar in that it specifies how +small components (called \emph{tokens}) can be put together to form +larger structures. In this section we will write a grammar for a tiny +subset of English. + +Simple English sentences can be described as being a noun phrase +followed by a verb followed by a noun phrase. For example, in the +sentence, ``Jack sank the blue ship,'' the word ``Jack'' is the first +noun phrase, ``sank'' is the verb, and ``the blue ship'' is the second +noun phrase. In addition we should say what a noun phrase is; for +this example we shall say that a noun phrase is an optional article +(a, an, the) followed by any number of adjectives followed by a noun. +The tokens in our language are the articles, nouns, verbs, and +adjectives. The \emph{rules} in our language will tell us how to +combine the tokens together to form lists of adjectives, noun phrases, +and sentences: + +\begin{itemize} + \item \texttt{sentence: noun\_phrase verb noun\_phrase} + \item \texttt{noun\_phrase: [article] adjective* noun} +\end{itemize} + +Notice that some things that we said easily in English, such as +``optional article,'' are expressed using special syntax, such as +brackets. When we said, ``any number of adjectives,'' we wrote +\texttt{adjective*}, where the \texttt{*} means ``zero or more of the +preceding pattern''. + +The grammar given above is close to a Yapps grammar. We also have to +specify what the tokens are, and what to do when a pattern is matched. +For this example, we will do nothing when patterns are matched; the +next example will explain how to perform match actions. + +\begin{verbatim} +parser TinyEnglish: + ignore: "\\W+" + token noun: "(Jack|spam|ship)" + token verb: "(sank|threw)" + token article: "(a|an|the)" + token adjective: "(blue|red|green)" + + rule sentence: noun_phrase verb noun_phrase + rule noun_phrase: [article] adjective* noun +\end{verbatim} + +The tokens are specified as Python \emph{regular expressions}. Since +Yapps produces Python code, you can write any regular expression that +would be accepted by Python. (\emph{Note:} These are Python 1.5 +regular expressions from the \texttt{re} module, not Python 1.4 +regular expressions from the \texttt{regex} module.) In addition to +tokens that you want to see (which are given names), you can also +specify tokens to ignore, marked by the \texttt{ignore} keyword. In +this parser we want to ignore whitespace. + +The TinyEnglish grammar shows how you define tokens and rules, but it +does not specify what should happen once we've matched the rules. In +the next example, we will take a grammar and produce a \emph{parse +tree} from it. + +\mysubsection{Lisp Expressions} + +Lisp syntax, although hated by many, has a redeeming quality: it is +simple to parse. In this section we will construct a Yapps grammar to +parse Lisp expressions and produce a parse tree as output. + +\subsubsection*{Defining the Grammar} + +The syntax of Lisp is simple. It has expressions, which are +identifiers, strings, numbers, and lists. A list is a left +parenthesis followed by some number of expressions (separated by +spaces) followed by a right parenthesis. For example, \verb|5|, +\verb|"ni"|, and \verb|(print "1+2 = " (+ 1 2))| are Lisp expressions. +Written as a grammar, + +\begin{verbatim} + expr: ID | STR | NUM | list + list: ( expr* ) +\end{verbatim} + +In addition to having a grammar, we need to specify what to do every +time something is matched. For the tokens, which are strings, we just +want to get the ``value'' of the token, attach its type (identifier, +string, or number) in some way, and return it. For the lists, we want +to construct and return a Python list. + +Once some pattern is matched, we enclose a return statement enclosed +in \verb|{{...}}|. The braces allow us to insert any one-line +statement into the parser. Within this statement, we can refer to the +values returned by matching each part of the rule. After matching a +token such as \texttt{ID}, ``ID'' will be bound to the text of the +matched token. Let's take a look at the rule: + +\begin{verbatim} + rule expr: ID {{ return ('id', ID) }} + ... +\end{verbatim} + +In a rule, tokens return the text that was matched. For identifiers, +we just return the identifier, along with a ``tag'' telling us that +this is an identifier and not a string or some other value. Sometimes +we may need to convert this text to a different form. For example, if +a string is matched, we want to remove quotes and handle special forms +like \verb|\n|. If a number is matched, we want to convert it into a +number. Let's look at the return values for the other tokens: + +\begin{verbatim} + ... + | STR {{ return ('str', eval(STR)) }} + | NUM {{ return ('num', atoi(NUM)) }} + ... +\end{verbatim} + +If we get a string, we want to remove the quotes and process any +special backslash codes, so we run \texttt{eval} on the quoted string. +If we get a number, we convert it to an integer with \texttt{atoi} and +then return the number along with its type tag. + +For matching a list, we need to do something slightly more +complicated. If we match a Lisp list of expressions, we want to +create a Python list with those values. + +\begin{verbatim} + rule list: "\\(" # Match the opening parenthesis + {{ result = [] }} # Create a Python list + ( + expr # When we match an expression, + {{ result.append(expr) }} # add it to the list + )* # * means repeat this if needed + "\\)" # Match the closing parenthesis + {{ return result }} # Return the Python list +\end{verbatim} + +In this rule we first match the opening parenthesis, then go into a +loop. In this loop we match expressions and add them to the list. +When there are no more expressions to match, we match the closing +parenthesis and return the resulting. Note that \verb:#: is used for +comments, just as in Python. + +The complete grammar is specified as follows: +\begin{verbatim} +parser Lisp: + ignore: '\\s+' + token NUM: '[0-9]+' + token ID: '[-+*/!@%^&=.a-zA-Z0-9_]+' + token STR: '"([^\\"]+|\\\\.)*"' + + rule expr: ID {{ return ('id', ID) }} + | STR {{ return ('str', eval(STR)) }} + | NUM {{ return ('num', atoi(NUM)) }} + | list {{ return list }} + rule list: "\\(" {{ result = [] }} + ( expr {{ result.append(expr) }} + )* + "\\)" {{ return result }} +\end{verbatim} + +One thing you may have noticed is that \verb|"\\("| and \verb|"\\)"| +appear in the \texttt{list} rule. These are \emph{inline tokens}: +they appear in the rules without being given a name with the +\texttt{token} keyword. Inline tokens are more convenient to use, but +since they do not have a name, the text that is matched cannot be used +in the return value. They are best used for short simple patterns +(usually punctuation or keywords). + +Another thing to notice is that the number and identifier tokens +overlap. For example, ``487'' matches both NUM and ID. In Yapps, the +scanner only tries to match tokens that are acceptable to the parser. +This rule doesn't help here, since both NUM and ID can appear in the +same place in the grammar. There are two rules used to pick tokens if +more than one matches. One is that the \emph{longest} match is +preferred. For example, ``487x'' will match as an ID (487x) rather +than as a NUM (487) followed by an ID (x). The second rule is that if +the two matches are the same length, the \emph{first} one listed in +the grammar is preferred. For example, ``487'' will match as an NUM +rather than an ID because NUM is listed first in the grammar. Inline +tokens have preference over any tokens you have listed. + +Now that our grammar is defined, we can run Yapps to produce a parser, +and then run the parser to produce a parse tree. + +\subsubsection*{Running Yapps} + +In the Yapps module is a function \texttt{generate} that takes an +input filename and writes a parser to another file. We can use this +function to generate the Lisp parser, which is assumed to be in +\texttt{lisp.g}. + +\begin{verbatim} +% python +Python 1.5.1 (#1, Sep 3 1998, 22:51:17) [GCC 2.7.2.3] on linux-i386 +Copyright 1991-1995 Stichting Mathematisch Centrum, Amsterdam +>>> import yapps +>>> yapps.generate('lisp.g') +\end{verbatim} + +At this point, Yapps has written a file \texttt{lisp.py} that contains +the parser. In that file are two classes (one scanner and one parser) +and a function (called \texttt{parse}) that puts things together for +you. + +Alternatively, we can run Yapps from the command line to generate the +parser file: + +\begin{verbatim} +% python yapps.py lisp.g +\end{verbatim} + +After running Yapps either from within Python or from the command +line, we can use the Lisp parser by calling the \texttt{parse} +function. The first parameter should be the rule we want to match, +and the second parameter should be the string to parse. + +\begin{verbatim} +>>> import lisp +>>> lisp.parse('expr', '(+ 3 4)') +[('id', '+'), ('num', 3), ('num', 4)] +>>> lisp.parse('expr', '(print "3 = " (+ 1 2))') +[('id', 'print'), ('str', '3 = '), [('id', '+'), ('num', 1), ('num', 2)]] +\end{verbatim} + +The \texttt{parse} function is not the only way to use the parser; +section \ref{sec:Parser-Objects} describes how to access parser objects +directly. + +We've now gone through the steps in creating a grammar, writing a +grammar file for Yapps, producing a parser, and using the parser. In +the next example we'll see how rules can take parameters and also how +to do computations instead of just returning a parse tree. + +\mysubsection{Calculator} + +A common example parser given in many textbooks is that for simple +expressions, with numbers, addition, subtraction, multiplication, +division, and parenthesization of subexpressions. We'll write this +example in Yapps, evaluating the expression as we parse. + +Unlike \texttt{yacc}, Yapps does not have any way to specify +precedence rules, so we have to do it ourselves. We say that an +expression is the sum of terms, and that a term is the product of +factors, and that a factor is a number or a parenthesized expression: + +\begin{verbatim} + expr: factor ( ("+"|"-") factor )* + factor: term ( ("*"|"/") term )* + term: NUM | "(" expr ")" +\end{verbatim} + +In order to evaluate the expression as we go, we should keep along an +accumulator while evaluating the lists of terms or factors. Just as +we kept a ``result'' variable to build a parse tree for Lisp +expressions, we will use a variable to evaluate numerical +expressions. The full grammar is given below: + +\begin{verbatim} +parser Calculator: + token END: "$" # $ means end of string + token NUM: "[0-9]+" + + rule goal: expr END {{ return expr }} + + # An expression is the sum and difference of factors + rule expr: factor {{ v = factor }} + ( "[+]" factor {{ v = v+factor }} + | "-" factor {{ v = v-factor }} + )* {{ return v }} + + # A factor is the product and division of terms + rule factor: term {{ v = term }} + ( "[*]" term {{ v = v*term }} + | "/" term {{ v = v/term }} + )* {{ return v }} + + # A term is either a number or an expression surrounded by parentheses + rule term: NUM {{ return atoi(NUM) }} + | "\\(" expr "\\)" {{ return expr }} +\end{verbatim} + +The top-level rule is \emph{goal}, which says that we are looking for +an expression followed by the end of the string. The \texttt{END} +token is needed because without it, it isn't clear when to stop +parsing. For example, the string ``1+3'' could be parsed either as +the expression ``1'' followed by the string ``+3'' or it could be +parsed as the expression ``1+3''. By requiring expressions to end +with \texttt{END}, the parser is forced to take ``1+3''. + +In the two rules with repetition, the accumulator is named \texttt{v}. +After reading in one expression, we initialize the accumulator. Each +time through the loop, we modify the accumulator by adding, +subtracting, multiplying by, or dividing the previous accumulator by +the expression that has been parsed. At the end of the rule, we +return the accumulator. + +The calculator example shows how to process lists of elements using +loops, as well as how to handle precedence of operators. + +\emph{Note:} It's often important to put the \texttt{END} token in, so +put it in unless you are sure that your grammar has some other +non-ambiguous token marking the end of the program. + +\mysubsection{Calculator with Memory} + +In the previous example we learned how to write a calculator that +evaluates simple numerical expressions. In this section we will +extend the example to support both local and global variables. + +To support global variables, we will add assignment statements to the +``goal'' rule. + +\begin{verbatim} + rule goal: expr END {{ return expr }} + | 'set' ID expr END {{ global_vars[ID] = expr }} + {{ return expr }} +\end{verbatim} + +To use these variables, we need a new kind of terminal: + +\begin{verbatim} + rule term: ... | ID {{ return global_vars[ID] }} +\end{verbatim} + +So far, these changes are straightforward. We simply have a global +dictionary \texttt{global\_vars} that stores the variables and values, +we modify it when there is an assignment statement, and we look up +variables in it when we see a variable name. + +To support local variables, we will add variable declarations to the +set of allowed expressions. + +\begin{verbatim} + rule term: ... | 'let' VAR '=' expr 'in' expr ... +\end{verbatim} + +This is where it becomes tricky. Local variables should be stored in +a local dictionary, not in the global one. One trick would be to save +a copy of the global dictionary, modify it, and then restore it +later. In this example we will instead use \emph{attributes} to +create local information and pass it to subrules. + +A rule can optionally take parameters. When we invoke the rule, we +must pass in arguments. For local variables, let's use a single +parameter, \texttt{local\_vars}: + +\begin{verbatim} + rule expr<>: ... + rule factor<>: ... + rule term<>: ... +\end{verbatim} + +Each time we want to match \texttt{expr}, \texttt{factor}, or +\texttt{term}, we will pass the local variables in the current rule to +the subrule. One interesting case is when we pass as an argument +something \emph{other} than \texttt{local\_vars}: + +\begin{verbatim} + rule term<>: ... + | 'let' VAR '=' expr<> + {{ local_vars = [(VAR, expr)] + local_vars }} + 'in' expr<> + {{ return expr }} +\end{verbatim} + +Note that the assignment to the local variables list does not modify +the original list. This is important to keep local variables from +being seen outside the ``let''. + +The other interesting case is when we find a variable: + +\begin{verbatim} +global_vars = {} + +def lookup(map, name): + for x,v in map: if x==name: return v + return global_vars[name] +%% + ... + rule term<: ... + | VAR {{ return lookup(local_vars, VAR) }} +\end{verbatim} + +The lookup function will search through the local variable list, and +if it cannot find the name there, it will look it up in the global +variable dictionary. + +A complete grammar for this example, including a read-eval-print loop +for interacting with the calculator, can be found in the examples +subdirectory included with Yapps. + +In this section we saw how to insert code before the parser. We also +saw how to use attributes to transmit local information from one rule +to its subrules. + +\mysection{Grammars} + +Each Yapps grammar has a name, a list of tokens, and a set of +production rules. A grammar named \texttt{X} will be used to produce +a parser named \texttt{X} and a scanner anmed \texttt{XScanner}. As +in Python, names are case sensitive, start with a letter, and contain +letters, numbers, and underscores (\_). + +There are three kinds of tokens in Yapps: named, inline, and ignored. +As their name implies, named tokens are given a name, using the token +construct: \texttt{token \emph{name} : \emph{regexp}}. In a rule, the +token can be matched by using the name. Inline tokens are regular +expressions that are used in rules without being declared. Ignored +tokens are declared using the ignore construct: \texttt{ignore: + \emph{regexp}}. These tokens are ignored by the scanner, and are +not seen by the parser. Often whitespace is an ignored token. The +regular expressions used to define tokens should use the syntax +defined in the \texttt{re} module, so some symbols may have to be +backslashed. + +Production rules in Yapps have a name and a pattern to match. If the +rule is parameterized, the name should be followed by a list of +parameter names in \verb|<<...>>|. A pattern can be a simple pattern +or a compound pattern. Simple patterns are the name of a named token, +a regular expression in quotes (inline token), the name of a +production rule (followed by arguments in \verb|<<...>>|, if the rule +has parameters), and single line Python statements (\verb|{{...}}|). +Compound patterns are sequences (\verb|A B C ...|), choices ( +\verb:A | B | C | ...:), options (\verb|[...]|), zero-or-more repetitions +(\verb|...*|), and one-or-more repetitions (\verb|...+|). Like +regular expressions, repetition operators have a higher precedence +than sequences, and sequences have a higher precedence than choices. + +Whenever \verb|{{...}}| is used, a legal one-line Python statement +should be put inside the braces. The token \verb|}}| should not +appear within the \verb|{{...}}| section, even within a string, since +Yapps does not attempt to parse the Python statement. A workaround +for strings is to put two strings together (\verb|"}" "}"|), or to use +backslashes (\verb|"}\}"|). At the end of a rule you should use a +\verb|{{ return X }}| statement to return a value. However, you +should \emph{not} use any control statements (\texttt{return}, +\texttt{continue}, \texttt{break}) in the middle of a rule. Yapps +needs to make assumptions about the control flow to generate a parser, +and any changes to the control flow will confuse Yapps. + +The \verb|<<...>>| form can occur in two places: to define parameters +to a rule and to give arguments when matching a rule. Parameters use +the syntax used for Python functions, so they can include default +arguments and the special forms (\verb|*args| and \verb|**kwargs|). +Arguments use the syntax for Python function call arguments, so they +can include normal arguments and keyword arguments. The token +\verb|>>| should not appear within the \verb|<<...>>| section. + +In both the statements and rule arguments, you can use names defined +by the parser to refer to matched patterns. You can refer to the text +matched by a named token by using the token name. You can use the +value returned by a production rule by using the name of that rule. +If a name \texttt{X} is matched more than once (such as in loops), you +will have to save the earlier value(s) in a temporary variable, and +then use that temporary variable in the return value. The next +section has an example of a name that occurs more than once. + +\mysubsection{Left Factoring} +\label{sec:Left-Factoring} + +Yapps produces ELL(1) parsers, which determine which clause to match +based on the first token available. Sometimes the leftmost tokens of +several clauses may be the same. The classic example is the +\emph{if/then/else} construct in Pascal: + +\begin{verbatim} +rule stmt: "if" expr "then" stmt {{ then_part = stmt }} + "else" stmt {{ return ('If',expr,then_part,stmt) }} + | "if" expr "then" stmt {{ return ('If',expr,stmt,[]) }} +\end{verbatim} + +(Note that we have to save the first \texttt{stmt} into a variable +because there is another \texttt{stmt} that will be matched.) The +left portions of the two clauses are the same, which presents a +problem for the parser. The solution is \emph{left-factoring}: the +common parts are put together, and \emph{then} a choice is made about +the remaining part: + +\begin{verbatim} +rule stmt: "if" expr + "then" stmt {{ then_part = stmt }} + {{ else_part = [] }} + [ "else" stmt {{ else_part = stmt }} ] + {{ return ('If', expr, then_part, else_part) }} +\end{verbatim} + +Unfortunately, the classic \emph{if/then/else} situation is +\emph{still} ambiguous when you left-factor. Yapps can deal with this +situation, but will report a warning; see section +\ref{sec:Ambiguous-Grammars} for details. + +In general, replace rules of the form: + +\begin{verbatim} +rule A: a b1 {{ return E1 }} + | a b2 {{ return E2 }} + | c3 {{ return E3 }} + | c4 {{ return E4 }} +\end{verbatim} + +with rules of the form: + +\begin{verbatim} +rule A: a ( b1 {{ return E1 }} + | b2 {{ return E2 }} + ) + | c3 {{ return E3 }} + | c4 {{ return E4 }} +\end{verbatim} + +\mysubsection{Left Recursion} + +A common construct in grammars is for matching a list of patterns, +sometimes separated with delimiters such as commas or semicolons. In +LR-based parser systems, we can parse a list with something like this: + +\begin{verbatim} +rule sum: NUM {{ return NUM }} + | sum "+" NUM {{ return (sum, NUM) }} +\end{verbatim} + +Parsing \texttt{1+2+3+4} would produce the output +\texttt{(((1,2),3),4)}, which is what we want from a left-associative +addition operator. Unfortunately, this grammar is \emph{left +recursive,} because the \texttt{sum} rule contains a clause that +begins with \texttt{sum}. (The recursion occurs at the left side of +the clause.) + +We must restructure this grammar to be \emph{right recursive} instead: + +\begin{verbatim} +rule sum: NUM {{ return NUM }} + | NUM "+" sum {{ return (NUM, sum) }} +\end{verbatim} + +Unfortunately, using this grammar, \texttt{1+2+3+4} would be parsed as +\texttt{(1,(2,(3,4)))}, which no longer follows left associativity. +The rule also needs to be left-factored. Instead, we write the +pattern as a loop instead: + +\begin{verbatim} +rule sum: NUM {{ v = NUM }} + ( "[+]" NUM {{ v = (v,NUM) }} )* + {{ return v }} +\end{verbatim} + +In general, replace rules of the form: + +\begin{verbatim} +rule A: A a1 -> << E1 >> + | A a2 -> << E2 >> + | b3 -> << E3 >> + | b4 -> << E4 >> +\end{verbatim} + +with rules of the form: + +\begin{verbatim} +rule A: ( b3 {{ A = E3 }} + | b4 {{ A = E4 }} ) + ( a1 {{ A = E1 }} + | a2 {{ A = E2 }} )* + {{ return A }} +\end{verbatim} + +We have taken a rule that proved problematic for with recursion and +turned it into a rule that works well with looping constructs. + +\mysubsection{Ambiguous Grammars} +\label{sec:Ambiguous-Grammars} + +In section \ref{sec:Left-Factoring} we saw the classic if/then/else +ambiguity, which occurs because the ``else \ldots'' portion of an ``if +\ldots then \ldots else \ldots'' construct is optional. Programs with +nested if/then/else constructs can be ambiguous when one of the else +clauses is missing: +\begin{verbatim} +if 1 then if 1 then + if 5 then if 5 then + x := 1; x := 1; + else else + y := 9; y := 9; +\end{verbatim} + +The indentation shows that the program can be parsed in two different +ways. (Of course, if we all would adopt Python's indentation-based +structuring, this would never happen!) Usually we want the parsing on +the left: the ``else'' should be associated with the closest ``if'' +statement. In section \ref{sec:Left-Factoring} we ``solved'' the +problem by using the following grammar: + +\begin{verbatim} +rule stmt: "if" expr + "then" stmt {{ then_part = stmt }} + {{ else_part = [] }} + [ "else" stmt {{ else_part = stmt }} ] + {{ return ('If', expr, then_part, else_part) }} +\end{verbatim} + +Here, we have an optional match of ``else'' followed by a statement. +The ambiguity is that if an ``else'' is present, it is not clear +whether you want it parsed immediately or if you want it to be parsed +by the outer ``if''. + +Yapps will deal with the situation by matching when the else pattern +when it can. The parser will work in this case because it prefers the +\emph{first} matching clause, which tells Yapps to parse the ``else''. +That is exactly what we want! + +For ambiguity cases with choices, Yapps will choose the \emph{first} +matching choice. However, remember that Yapps only looks at the first +token to determine its decision, so {\tt (a b | a c)} will result in +Yapps choosing {\tt a b} even when the input is {\tt a c}. It only +looks at the first token, {\tt a}, to make its decision. + +\mysection{Customization} + +Both the parsers and the scanners can be customized. The parser is +usually extended by subclassing, and the scanner can either be +subclassed or completely replaced. + +\mysubsection{Customizing Parsers} + +If additional fields and methods are needed in order for a parser to +work, Python subclassing can be used. (This is unlike parser classes +written in static languages, in which these fields and methods must be +defined in the generated parser class.) We simply subclass the +generated parser, and add any fields or methods required. Expressions +in the grammar can call methods of the subclass to perform any actions +that cannot be expressed as a simple expression. For example, +consider this simple grammar: + +\begin{verbatim} +parser X: + rule goal: "something" {{ self.printmsg() }} +\end{verbatim} + +The \texttt{printmsg} function need not be implemented in the parser +class \texttt{X}; it can be implemented in a subclass: + +\begin{verbatim} +import Xparser + +class MyX(Xparser.X): + def printmsg(self): + print "Hello!" +\end{verbatim} + +\mysubsection{Customizing Scanners} + +The generated parser class is not dependent on the generated scanner +class. A scanner object is passed to the parser object's constructor +in the \texttt{parse} function. To use a different scanner, write +your own function to construct parser objects, with an instance of a +different scanner. Scanner objects must have a \texttt{token} method +that accepts an integer \texttt{N} as well as a list of allowed token +types, and returns the Nth token, as a tuple. The default scanner +raises \texttt{NoMoreTokens} if no tokens are available, and +\texttt{SyntaxError} if no token could be matched. However, the +parser does not rely on these exceptions; only the \texttt{parse} +convenience function (which calls \texttt{wrap\_error\_reporter}) and +the \texttt{print\_error} error display function use those exceptions. + +The tuples representing tokens have four elements. The first two are +the beginning and ending indices of the matched text in the input +string. The third element is the type tag, matching either the name +of a named token or the quoted regexp of an inline or ignored token. +The fourth element of the token tuple is the matched text. If the +input string is \texttt{s}, and the token tuple is +\texttt{(b,e,type,val)}, then \texttt{val} should be equal to +\texttt{s[b:e]}. + +The generated parsers do not the beginning or ending index. They use +only the token type and value. However, the default error reporter +uses the beginning and ending index to show the user where the error +is. + +\mysection{Parser Mechanics} + +The base parser class (Parser) defines two methods, \texttt{\_scan} +and \texttt{\_peek}, and two fields, \texttt{\_pos} and +\texttt{\_scanner}. The generated parser inherits from the base +parser, and contains one method for each rule in the grammar. To +avoid name clashes, do not use names that begin with an underscore +(\texttt{\_}). + +\mysubsection{Parser Objects} +\label{sec:Parser-Objects} + +Yapps produces as output two exception classes, a scanner class, a +parser class, and a function \texttt{parse} that puts everything +together. The \texttt{parse} function does not have to be used; +instead, one can create a parser and scanner object and use them +together for parsing. + +\begin{verbatim} + def parse(rule, text): + P = X(XScanner(text)) + return wrap_error_reporter(P, rule) +\end{verbatim} + +The \texttt{parse} function takes a name of a rule and an input string +as input. It creates a scanner and parser object, then calls +\texttt{wrap\_error\_reporter} to execute the method in the parser +object named \texttt{rule}. The wrapper function will call the +appropriate parser rule and report any parsing errors to standard +output. + +There are several situations in which the \texttt{parse} function +would not be useful. If a different parser or scanner is being used, +or exceptions are to be handled differently, a new \texttt{parse} +function would be required. The supplied \texttt{parse} function can +be used as a template for writing a function for your own needs. An +example of a custom parse function is the \texttt{generate} function +in \texttt{Yapps.py}. + +\mysubsection{Context Sensitive Scanner} + +Unlike most scanners, the scanner produced by Yapps can take into +account the context in which tokens are needed, and try to match only +good tokens. For example, in the grammar: + +\begin{verbatim} +parser IniFile: + token ID: "[a-zA-Z_0-9]+" + token VAL: ".*" + + rule pair: ID "[ \t]*=[ \t]*" VAL "\n" +\end{verbatim} + +we would like to scan lines of text and pick out a name/value pair. +In a conventional scanner, the input string \texttt{shell=progman.exe} +would be turned into a single token of type \texttt{VAL}. The Yapps +scanner, however, knows that at the beginning of the line, an +\texttt{ID} is expected, so it will return \texttt{"shell"} as a token +of type \texttt{ID}. Later, it will return \texttt{"progman.exe"} as +a token of type \texttt{VAL}. + +Context sensitivity decreases the separation between scanner and +parser, but it is useful in parsers like \texttt{IniFile}, where the +tokens themselves are not unambiguous, but \emph{are} unambiguous +given a particular stage in the parsing process. + +Unfortunately, context sensitivity can make it more difficult to +detect errors in the input. For example, in parsing a Pascal-like +language with ``begin'' and ``end'' as keywords, a context sensitive +scanner would only match ``end'' as the END token if the parser is in +a place that will accept the END token. If not, then the scanner +would match ``end'' as an identifier. To disable the context +sensitive scanner in Yapps, add the +\texttt{context-insensitive-scanner} option to the grammar: + +\begin{verbatim} +Parser X: + option: "context-insensitive-scanner" +\end{verbatim} + +Context-insensitive scanning makes the parser look cleaner as well. + +\mysubsection{Internal Variables} + +There are two internal fields that may be of use. The parser object +has two fields, \texttt{\_pos}, which is the index of the current +token being matched, and \texttt{\_scanner}, which is the scanner +object. The token itself can be retrieved by accessing the scanner +object and calling the \texttt{token} method with the token index. However, if you call \texttt{token} before the token has been requested by the parser, it may mess up a context-sensitive scanner.\footnote{When using a context-sensitive scanner, the parser tells the scanner what the valid token types are at each point. If you call \texttt{token} before the parser can tell the scanner the valid token types, the scanner will attempt to match without considering the context.} A +potentially useful combination of these fields is to extract the +portion of the input matched by the current rule. To do this, just save the scanner state (\texttt{\_scanner.pos}) before the text is matched and then again after the text is matched: + +\begin{verbatim} + rule R: + {{ start = self._scanner.pos }} + a b c + {{ end = self._scanner.pos }} + {{ print 'Text is', self._scanner.input[start:end] }} +\end{verbatim} + +\mysubsection{Pre- and Post-Parser Code} + +Sometimes the parser code needs to rely on helper variables, +functions, and classes. A Yapps grammar can optionally be surrounded +by double percent signs, to separate the grammar from Python code. + +\begin{verbatim} +... Python code ... +%% +... Yapps grammar ... +%% +... Python code ... +\end{verbatim} + +The second \verb|%%| can be omitted if there is no Python code at the +end, and the first \verb|%%| can be omitted if there is no extra +Python code at all. (To have code only at the end, both separators +are required.) + +If the second \verb|%%| is omitted, Yapps will insert testing code +that allows you to use the generated parser to parse a file. + +The extended calculator example in the Yapps examples subdirectory +includes both pre-parser and post-parser code. + +\mysubsection{Representation of Grammars} + +For each kind of pattern there is a class derived from Pattern. Yapps +has classes for Terminal, NonTerminal, Sequence, Choice, Option, Plus, +Star, and Eval. Each of these classes has the following interface: + +\begin{itemize} + \item[setup(\emph{gen})] Set accepts-$\epsilon$, and call + \emph{gen.changed()} if it changed. This function can change the + flag from false to true but \emph{not} from true to false. + \item[update(\emph(gen))] Set \first and \follow, and call + \emph{gen.changed()} if either changed. This function can add to + the sets but \emph{not} remove from them. + \item[output(\emph{gen}, \emph{indent})] Generate code for matching + this rule, using \emph{indent} as the current indentation level. + Writes are performed using \emph{gen.write}. + \item[used(\emph{vars})] Given a list of variables \emph{vars}, + return two lists: one containing the variables that are used, and + one containing the variables that are assigned. This function is + used for optimizing the resulting code. +\end{itemize} + +Both \emph{setup} and \emph{update} monotonically increase the +variables they modify. Since the variables can only increase a finite +number of times, we can repeatedly call the function until the +variable stabilized. The \emph{used} function is not currently +implemented. + +With each pattern in the grammar Yapps associates three pieces of +information: the \first set, the \follow set, and the +accepts-$\epsilon$ flag. + +The \first set contains the tokens that can appear as we start +matching the pattern. The \follow set contains the tokens that can +appear immediately after we match the pattern. The accepts-$\epsilon$ +flag is true if the pattern can match no tokens. In this case, \first +will contain all the elements in \follow. The \follow set is not +needed when accepts-$\epsilon$ is false, and may not be accurate in +those cases. + +Yapps does not compute these sets precisely. Its approximation can +miss certain cases, such as this one: + +\begin{verbatim} + rule C: ( A* | B ) + rule B: C [A] +\end{verbatim} + +Yapps will calculate {\tt C}'s \follow set to include {\tt A}. +However, {\tt C} will always match all the {\tt A}'s, so {\tt A} will +never follow it. Yapps 2.0 does not properly handle this construct, +but if it seems important, I may add support for it in a future +version. + +Yapps also cannot handle constructs that depend on the calling +sequence. For example: + +\begin{verbatim} + rule R: U | 'b' + rule S: | 'c' + rule T: S 'b' + rule U: S 'a' +\end{verbatim} + +The \follow set for {\tt S} includes {\tt a} and {\tt b}. Since {\tt + S} can be empty, the \first set for {\tt S} should include {\tt a}, +{\tt b}, and {\tt c}. However, when parsing {\tt R}, if the lookahead +is {\tt b} we should \emph{not} parse {\tt U}. That's because in {\tt + U}, {\tt S} is followed by {\tt a} and not {\tt b}. Therefore in +{\tt R}, we should choose rule {\tt U} only if there is an {\tt a} or +{\tt c}, but not if there is a {\tt b}. Yapps and many other LL(1) +systems do not distinguish {\tt S b} and {\tt S a}, making {\tt + S}'s \follow set {\tt a, b}, and making {\tt R} always try to match +{\tt U}. In this case we can solve the problem by changing {\tt R} to +\verb:'b' | U: but it may not always be possible to solve all such +problems in this way. + +\appendix + +\mysection{Grammar for Parsers} + +This is the grammar for parsers, without any Python code mixed in. +The complete grammar can be found in \texttt{parsedesc.g} in the Yapps +distribution. + +\begin{verbatim} +parser ParserDescription: + ignore: "\\s+" + ignore: "#.*?\r?\n" + token END: "$" # $ means end of string + token ATTR: "<<.+?>>" + token STMT: "{{.+?}}" + token ID: '[a-zA-Z_][a-zA-Z_0-9]*' + token STR: '[rR]?\'([^\\n\'\\\\]|\\\\.)*\'|[rR]?"([^\\n"\\\\]|\\\\.)*"' + + rule Parser: "parser" ID ":" + Options + Tokens + Rules + END + + rule Options: ( "option" ":" STR )* + rule Tokens: ( "token" ID ":" STR | "ignore" ":" STR )* + rule Rules: ( "rule" ID OptParam ":" ClauseA )* + + rule ClauseA: ClauseB ( '[|]' ClauseB )* + rule ClauseB: ClauseC* + rule ClauseC: ClauseD [ '[+]' | '[*]' ] + rule ClauseD: STR | ID [ATTR] | STMT + | '\\(' ClauseA '\\) | '\\[' ClauseA '\\]' +\end{verbatim} + +\mysection{Upgrading} + +Yapps 2.0 is not backwards compatible with Yapps 1.0. In this section +are some tips for upgrading: + +\begin{enumerate} + \item Yapps 1.0 was distributed as a single file. Yapps 2.0 is + instead distributed as two Python files: a \emph{parser generator} + (26k) and a \emph{parser runtime} (5k). You need both files to + create parsers, but you need only the runtime (\texttt{yappsrt.py}) + to use the parsers. + + \item Yapps 1.0 supported Python 1.4 regular expressions from the + \texttt{regex} module. Yapps 2.0 uses Python 1.5 regular + expressions from the \texttt{re} module. \emph{The new syntax for + regular expressions is not compatible with the old syntax.} + Andrew Kuchling has a \htmladdnormallink{guide to converting + regular + expressions}{http://www.python.org/doc/howto/regex-to-re/} on his + web page. + + \item Yapps 1.0 wants a pattern and then a return value in \verb|->| + \verb|<<...>>|. Yapps 2.0 allows patterns and Python statements to + be mixed. To convert a rule like this: + +\begin{verbatim} +rule R: A B C -> << E1 >> + | X Y Z -> << E2 >> +\end{verbatim} + + to Yapps 2.0 form, replace the return value specifiers with return + statements: + +\begin{verbatim} +rule R: A B C {{ return E1 }} + | X Y Z {{ return E2 }} +\end{verbatim} + + \item Yapps 2.0 does not perform tail recursion elimination. This + means any recursive rules you write will be turned into recursive + methods in the parser. The parser will work, but may be slower. + It can be made faster by rewriting recursive rules, using instead + the looping operators \verb|*| and \verb|+| provided in Yapps 2.0. + +\end{enumerate} + +\mysection{Troubleshooting} + +\begin{itemize} + \item A common error is to write a grammar that doesn't have an END + token. End tokens are needed when it is not clear when to stop + parsing. For example, when parsing the expression {\tt 3+5}, it is + not clear after reading {\tt 3} whether to treat it as a complete + expression or whether the parser should continue reading. + Therefore the grammar for numeric expressions should include an end + token. Another example is the grammar for Lisp expressions. In + Lisp, it is always clear when you should stop parsing, so you do + \emph{not} need an end token. In fact, it may be more useful not + to have an end token, so that you can read in several Lisp expressions. + \item If there is a chance of ambiguity, make sure to put the choices + in the order you want them checked. Usually the most specific + choice should be first. Empty sequences should usually be last. + \item The context sensitive scanner is not appropriate for all + grammars. You might try using the insensitive scanner with the + {\tt context-insensitive-scanner} option in the grammar. + \item If performance turns out to be a problem, try writing a custom + scanner. The Yapps scanner is rather slow (but flexible and easy + to understand). +\end{itemize} + +\mysection{History} + +Yapps 1 had several limitations that bothered me while writing +parsers: + +\begin{enumerate} + \item It was not possible to insert statements into the generated + parser. A common workaround was to write an auxilliary function + that executed those statements, and to call that function as part + of the return value calculation. For example, several of my + parsers had an ``append(x,y)'' function that existed solely to call + ``x.append(y)''. + \item The way in which grammars were specified was rather + restrictive: a rule was a choice of clauses. Each clause was a + sequence of tokens and rule names, followed by a return value. + \item Optional matching had to be put into a separate rule because + choices were only made at the beginning of a rule. + \item Repetition had to be specified in terms of recursion. Not only + was this awkward (sometimes requiring additional rules), I had to + add a tail recursion optimization to Yapps to transform the + recursion back into a loop. +\end{enumerate} + +Yapps 2 addresses each of these limitations. + +\begin{enumerate} + \item Statements can occur anywhere within a rule. (However, only + one-line statements are allowed; multiline blocks marked by + indentation are not.) + \item Grammars can be specified using any mix of sequences, choices, + tokens, and rule names. To allow for complex structures, + parentheses can be used for grouping. + \item Given choices and parenthesization, optional matching can be + expressed as a choice between some pattern and nothing. In + addition, Yapps 2 has the convenience syntax \verb|[A B ...]| for + matching \verb|A B ...| optionally. + \item Repetition operators \verb|*| for zero or more and \verb|+| for + one or more make it easy to specify repeating patterns. +\end{enumerate} + +It is my hope that Yapps 2 will be flexible enough to meet my needs +for another year, yet simple enough that I do not hesitate to use it. + +\mysection{Future Extensions} +\label{sec:future} + +I am still investigating the possibility of LL(2) and higher +lookahead. However, it looks like the resulting parsers will be +somewhat ugly. + +It would be nice to control choices with user-defined predicates. + +The most likely future extension is backtracking. A grammar pattern +like \verb|(VAR ':=' expr)? {{ return Assign(VAR,expr) }} : expr {{ return expr }}| +would turn into code that attempted to match \verb|VAR ':=' expr|. If +it succeeded, it would run \verb|{{ return ... }}|. If it failed, it +would match \verb|expr {{ return expr }}|. Backtracking may make it +less necessary to write LL(2) grammars. + +\mysection{References} + +\begin{enumerate} + \item The \htmladdnormallink{Python-Parser + SIG}{http://www.python.org/sigs/parser-sig/} is the first place + to look for a list of parser systems for Python. + + \item ANTLR/PCCTS, by Terrence Parr, is available at + \htmladdnormallink{The ANTLR Home Page}{http://www.antlr.org/}. + + \item PyLR, by Scott Cotton, is at \htmladdnormallink{his Starship + page}{http://starship.skyport.net/crew/scott/PyLR.html}. + + \item John Aycock's \htmladdnormallink{Compiling Little Languages + Framework}{http://www.csr.UVic.CA/~aycock/python/}. + + \item PyBison, by Scott Hassan, can be found at + \htmladdnormallink{his Python Projects + page}{http://coho.stanford.edu/\~{}hassan/Python/}. + + \item mcf.pars, by Mike C. Fletcher, is available at + \htmladdnormallink{his web + page}{http://www.golden.net/\~{}mcfletch/programming/}. + + \item kwParsing, by Aaron Watters, is available at + \htmladdnormallink{his Starship + page}{http://starship.skyport.net/crew/aaron_watters/kwParsing/}. +\end{enumerate} + +\end{document} diff --git a/util/sconfig/yappsrt.py b/util/sconfig/yappsrt.py new file mode 100644 index 0000000..2ce2480 --- /dev/null +++ b/util/sconfig/yappsrt.py @@ -0,0 +1,172 @@ +# Yapps 2.0 Runtime +# +# This module is needed to run generated parsers. + +from string import * +import exceptions +import re + +class SyntaxError(Exception): + """When we run into an unexpected token, this is the exception to use""" + def __init__(self, pos=-1, msg="Bad Token"): + self.pos = pos + self.msg = msg + def __repr__(self): + if self.pos < 0: return "#" + else: return "SyntaxError[@ char " + `self.pos` + ": " + self.msg + "]" + +class NoMoreTokens(Exception): + """Another exception object, for when we run out of tokens""" + pass + +class Scanner: + def __init__(self, patterns, ignore, input): + """Patterns is [(terminal,regex)...] + Ignore is [terminal,...]; + Input is a string""" + self.tokens = [] + self.restrictions = [] + self.input = input + self.pos = 0 + self.ignore = ignore + # The stored patterns are a pair (compiled regex,source + # regex). If the patterns variable passed in to the + # constructor is None, we assume that the class already has a + # proper .patterns list constructed + if patterns is not None: + self.patterns = [] + for k,r in patterns: + self.patterns.append( (k, re.compile(r)) ) + + def token(self, i, restrict=0): + """Get the i'th token, and if i is one past the end, then scan + for another token; restrict is a list of tokens that + are allowed, or 0 for any token.""" + if i == len(self.tokens): self.scan(restrict) + if i < len(self.tokens): + # Make sure the restriction is more restricted + if restrict and self.restrictions[i]: + for r in restrict: + if r not in self.restrictions[i]: + raise "Unimplemented: restriction set changed" + return self.tokens[i] + raise NoMoreTokens() + + def __repr__(self): + """Print the last 10 tokens that have been scanned in""" + output = '' + for t in self.tokens[-10:]: + output = '%s\n (@%s) %s = %s' % (output,t[0],t[2],`t[3]`) + return output + + def scan(self, restrict): + """Should scan another token and add it to the list, self.tokens, + and add the restriction to self.restrictions""" + # Keep looking for a token, ignoring any in self.ignore + while 1: + # Search the patterns for the longest match, with earlier + # tokens in the list having preference + best_match = -1 + best_pat = '(error)' + for p, regexp in self.patterns: + # First check to see if we're ignoring this token + if restrict and p not in restrict and p not in self.ignore: + continue + m = regexp.match(self.input, self.pos) + if m and len(m.group(0)) > best_match: + # We got a match that's better than the previous one + best_pat = p + best_match = len(m.group(0)) + + # If we didn't find anything, raise an error + if best_pat == '(error)' and best_match < 0: + msg = "Bad Token" + if restrict: + msg = "Trying to find one of "+join(restrict,", ") + raise SyntaxError(self.pos, msg) + + # If we found something that isn't to be ignored, return it + if best_pat not in self.ignore: + # Create a token with this data + token = (self.pos, self.pos+best_match, best_pat, + self.input[self.pos:self.pos+best_match]) + self.pos = self.pos + best_match + # Only add this token if it's not in the list + # (to prevent looping) + if not self.tokens or token != self.tokens[-1]: + self.tokens.append(token) + self.restrictions.append(restrict) + return + else: + # This token should be ignored .. + self.pos = self.pos + best_match + +class Parser: + def __init__(self, scanner): + self._scanner = scanner + self._pos = 0 + + def _peek(self, *types): + """Returns the token type for lookahead; if there are any args + then the list of args is the set of token types to allow""" + tok = self._scanner.token(self._pos, types) + return tok[2] + + def _scan(self, type): + """Returns the matched text, and moves to the next token""" + tok = self._scanner.token(self._pos, [type]) + if tok[2] != type: + raise SyntaxError(tok[0], 'Trying to find '+type) + self._pos = 1+self._pos + return tok[3] + + + +def print_error(input, err, scanner): + """This is a really dumb long function to print error messages nicely.""" + p = err.pos + # Figure out the line number + line = count(input[:p], '\n') + print err.msg+" on line "+`line+1`+":" + # Now try printing part of the line + text = input[max(p-80,0):p+80] + p = p - max(p-80,0) + + # Strip to the left + i = rfind(text[:p],'\n') + j = rfind(text[:p],'\r') + if i < 0 or (j < i and j >= 0): i = j + if i >= 0 and i < p: + p = p - i - 1 + text = text[i+1:] + + # Strip to the right + i = find(text,'\n',p) + j = find(text,'\r',p) + if i < 0 or (j < i and j >= 0): i = j + if i >= 0: + text = text[:i] + + # Now shorten the text + while len(text) > 70 and p > 60: + # Cut off 10 chars + text = "..." + text[10:] + p = p - 7 + + # Now print the string, along with an indicator + print '> ',text + print '> ',' '*p + '^' + print 'List of nearby tokens:', scanner + +def wrap_error_reporter(parser, rule): + try: return getattr(parser, rule)() + except SyntaxError, s: + input = parser._scanner.input + try: + print_error(input, s, parser._scanner) + except ImportError: + print 'Syntax Error',s.msg,'on line',1+count(input[:s.pos], '\n') + except NoMoreTokens: + print 'Could not complete parsing; stopped around here:' + print parser._scanner + -- cgit v1.1