Padawitz, Peter2016-09-302016-09-301978https://depositonce.tu-berlin.de/handle/11303/5915http://dx.doi.org/10.14279/depositonce-5508Dieser Bericht ist im Wortlaut identisch mit: Peter Padawitz, Church-Rosser-Eigenschaften von Graph-Grammatiken und Anwendungen auf die Semantik von LISP, Diplomarbeit 1978.Previous studies of operational versus functional semantics of symbolic expressions mostly have been confined to treelike expressions and evaluation by "simplification" and substitution of recursive definitions for function symbols. In order to drop these restrictions we introduce Σ-graphs and Σ-grammars to represent expressions and evaluation rules, respectively. Functional semantics of Σ-graphs is defined as an extension of Scott's fixed point semantics of flow diagrams. We prove that derivations via a Σ-grammar P preserve the functional semantics of Σ-graphs if the underlying "semantic algebra" satisfies the equations given by P. To get an operational semantics of a Σ-graph G relative to a Σ-grammar P derivations of G via P must yield a unique normal form. Therefore sufficient conditions for a weak Church-Rosser property of Σ-grammars are formulated and proved for some classes of such grammars. Applying these results to the programming language LISP we show that the evaluation rules of a LISP interpreter are compatible with the semantics of LISP and weak Church-Rosser where garbage collection is included.de004 Datenverarbeitung; Informatiksemanticsn-graphsLISPChurch-RosserSemantikGraph-GrammatikenChurch-Rosser-EigenschaftenResearch Paper