Parse Trees for Context-Free Parallel Communicating Grammar Systems*

摘要

Parallel communicating grammar systems (PCGS) have been introduced awhile ago purportedly to analyze concurrent systems on a language-theoretic level. To our knowledge however no actual relationship between PCGS and practical computing systems was ever investigated. We believe that PGCS have high practical potential, especially in the area of formal methods. Therefore we are starting to bring parallel communicating grammar systems to a more practical level by introducing a construct that has proven useful elsewhere (in context-free grammars and parsing), namely the parse tree. We show that every derivation in a PCGS has a corresponding parse forest (a set of parse trees); we also argue that one parse tree (rather than a parse forest) may actually be sufficient in some circumstances to capture the properties of the derivation. In addition, we find out that the properties of PCGS parse forests for different kinds of PCGS suggest a particular PCGS variant as being the most suitable for practical applications.