branch: externals/parser-generator
commit 89105668e8869ef533e020a746e85bf3f5fd2b24
Author: Christian Johansson <christ...@cvj.se>
Commit: Christian Johansson <christ...@cvj.se>
Started on LL(k) implementation
---
Makefile | 6 +++-
parser-generator-ll.el | 67 ++++++++++++++++++++++++++++++++++++++++
parser-generator-lr.el | 4 +--
test/parser-generator-ll-test.el | 53 +++++++++++++++++++++++++++++++
4 files changed, 127 insertions(+), 3 deletions(-)
diff --git a/Makefile b/Makefile
index 4965a61a20..0a0c777f40 100644
--- a/Makefile
+++ b/Makefile
@@ -4,7 +4,7 @@ ifdef emacs
endif
EMACS_CMD := $(EMACS) -Q -batch -L . -L test/
-EL := parser-generator.el parser-generator-lex-analyzer.el
parser-generator-lr.el parser-generator-lr-export.el
test/parser-generator-test.el test/parser-generator-lex-analyzer-test.el
test/parser-generator-lr-export-test.el test/parser-generator-lr-test.el
+EL := parser-generator.el parser-generator-lex-analyzer.el
parser-generator-ll.el parser-generator-lr.el parser-generator-lr-export.el
test/parser-generator-test.el test/parser-generator-lex-analyzer-test.el
test/parser-generator-lr-export-test.el test/parser-generator-ll-test.el
test/parser-generator-lr-test.el
ELC := $(EL:.el=.elc)
.PHONY: clean
@@ -27,6 +27,10 @@ test-lex-analyzer:
test-lr:
$(EMACS_CMD) -l test/parser-generator-lr-test.el -f
"parser-generator-lr-test"
+.PHONY: test-ll
+test-ll:
+ $(EMACS_CMD) -l test/parser-generator-ll-test.el -f
"parser-generator-ll-test"
+
.PHONY: test-lr-export
test-lr-export:
$(EMACS_CMD) -l test/parser-generator-lr-export-test.el -f
"parser-generator-lr-export-test"
diff --git a/parser-generator-ll.el b/parser-generator-ll.el
new file mode 100644
index 0000000000..c488f3af48
--- /dev/null
+++ b/parser-generator-ll.el
@@ -0,0 +1,67 @@
+;;; parser-generator-ll.el --- LL(k) Parser Generator -*- lexical-binding: t
-*-
+
+;; Copyright (C) 2020-2022 Free Software Foundation, Inc.
+
+
+;;; Commentary:
+
+
+;;; Code:
+
+
+(require 'parser-generator)
+(require 'parser-generator-lex-analyzer)
+
+
+;;; Variables:
+
+
+(defvar
+ parser-generator-ll--parsing-table
+ nil
+ "Parsing-table for grammar.")
+
+
+;;; Functions
+
+
+(defun parser-generator-ll-generate-parser-tables ()
+ "Generate parsing tables for grammar."
+ (message "\n;; Starting generation of LL(k) parser-tables..\n")
+ (unless (parser-generator-ll--valid-llk-p parser-generator--grammar)
+ (error "Invalid grammar specified!"))
+ (let* ((tables (parser-generator-ll--generate-tables))
+ (parsing-table (parser-generator-ll--generate-parsing-table)))
+ (setq
+ parser-generator-ll--parsing-table
+ parsing-table)
+ (message "\n;; Completed generation of LL(k) parser-tables.\n")))
+
+
+;;; Algorithms
+
+
+;; TODO
+;; Algorithm 5.2 p. 350
+(defun parser-generator-ll--generate-tables ()
+ "Construction of LL(k)-tables. Output the set of LL(k) tables needed to
construct a parsing table for the grammar G."
+ )
+
+
+;; TODO
+;; Algorithm 5.3 p. 351
+(defun parser-generator-ll--generate-parsing-table ()
+ "A parsing table for an LL(k) grammar G. Output M, a valid parsing table
for G."
+ )
+
+
+;; TODO
+;; Algorithm 5.4 p. 357
+(defun parser-generator-ll--valid-grammar-p ()
+ "Test for LL(k)-ness. Output t if grammar G is LL(k). nil otherwise."
+ )
+
+
+(provide 'parser-generator-ll)
+
+;;; parser-generator-ll.el ends here
diff --git a/parser-generator-lr.el b/parser-generator-lr.el
index d57f691906..47c0baa3b3 100644
--- a/parser-generator-lr.el
+++ b/parser-generator-lr.el
@@ -254,13 +254,13 @@
(defun parser-generator-lr-generate-parser-tables ()
"Generate parsing tables for grammar."
- (message "\n;; Starting generation of parser-tables..\n")
+ (message "\n;; Starting generation of LR(k) parser-tables..\n")
(parser-generator-lr--generate-precedence-tables)
(let ((table-lr-items
(parser-generator-lr--generate-goto-tables)))
(parser-generator-lr--generate-action-tables
table-lr-items)
- (message "\n;; Completed generation of parser-tables.\n")
+ (message "\n;; Completed generation of LR(k) parser-tables.\n")
table-lr-items))
(defun parser-generator-lr--get-expanded-action-tables ()
diff --git a/test/parser-generator-ll-test.el b/test/parser-generator-ll-test.el
new file mode 100644
index 0000000000..9c13d1fc95
--- /dev/null
+++ b/test/parser-generator-ll-test.el
@@ -0,0 +1,53 @@
+;; parser-generator-ll-test.el --- Tests for LL(k) Parser Generator -*-
lexical-binding: t -*-
+
+;; Copyright (C) 2020-2022 Free Software Foundation, Inc.
+
+
+;;; Commentary:
+
+
+;;; Code:
+
+
+(require 'parser-generator-ll)
+(require 'ert)
+
+(defun parser-generator-ll-test--generate-tables ()
+ "Test `parser-generator-ll--generate-tables'."
+ (message "Started tests for (parser-generator-ll--generate-tables)")
+
+
+ (message "Passed tests for (parser-generator-ll--generate-tables)"))
+
+(defun parser-generator-ll-test--generate-parsing-table ()
+ "Test `parser-generator-ll--generate-parsing-table'."
+ (message "Started tests for (parser-generator-ll--generate-parsing-table)")
+
+
+ (message "Passed tests for (parser-generator-ll--generate-parsing-table)"))
+
+(defun parser-generator-ll-test--valid-grammar-p ()
+ "Test `parser-generator-ll--valid-grammar-p'."
+ (message "Started tests for (parser-generator-ll--valid-grammar-p)")
+
+
+ (message "Passed tests for (parser-generator-ll--valid-grammar-p)"))
+
+(defun parser-generator-ll-test-generate-parser-tables ()
+ "Test `parser-generator-ll-generate-parser-tables'."
+ (message "Started tests for (parser-generator-ll-generate-parser-tables)")
+
+
+ (message "Passed tests for (parser-generator-ll-generate-parser-tables)"))
+
+(defun parser-generator-ll-test ()
+ "Run test."
+ (parser-generator-ll-test--generate-tables)
+ (parser-generator-ll-test--generate-parsing-table)
+ (parser-generator-ll-test--valid-grammar-p)
+ (parser-generator-ll-test-generate-parser-tables))
+
+
+(provide 'parser-generator-ll-test)
+
+;;; parser-generator-ll-test.el ends here
