summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorYuichiro Kaneko <spiketeika@gmail.com>2023-05-12 18:25:10 +0900
committerGitHub <noreply@github.com>2023-05-12 18:25:10 +0900
commita1b01e7701f9fc370f8dff777aad6d39a2c5a3e3 (patch)
tree69bb0c08c139f1c7c5abe9422649f11581f85529
parentd314fe42f987fcfaad67f102ec418ee4ca32ee99 (diff)
Use Lrama LALR parser generator instead of Bisonv3_3_0_preview1
https://bugs.ruby-lang.org/issues/19637 Co-authored-by: Nobuyoshi Nakada <nobu@ruby-lang.org>
Notes
Notes: Merged: https://github.com/ruby/ruby/pull/7798 Merged-By: yui-knk <spiketeika@gmail.com>
-rw-r--r--.github/workflows/baseruby.yml2
-rw-r--r--.github/workflows/bundled_gems.yml2
-rw-r--r--.github/workflows/check_dependencies.yml2
-rw-r--r--.github/workflows/codeql-analysis.yml2
-rw-r--r--.github/workflows/macos.yml3
-rw-r--r--.github/workflows/mingw.yml4
-rw-r--r--.github/workflows/rjit-bindgen.yml2
-rw-r--r--.github/workflows/rjit.yml2
-rw-r--r--.github/workflows/ubuntu.yml2
-rw-r--r--.github/workflows/wasm.yml2
-rw-r--r--.github/workflows/windows.yml1
-rw-r--r--.github/workflows/yjit-ubuntu.yml2
-rw-r--r--common.mk7
-rw-r--r--defs/gmake.mk1
-rw-r--r--doc/contributing/building_ruby.md1
-rw-r--r--doc/windows.md7
-rw-r--r--ext/ripper/depend2
-rw-r--r--ext/ripper/extconf.rb10
-rw-r--r--template/Makefile.in2
-rwxr-xr-xtool/lrama/exe/lrama7
-rw-r--r--tool/lrama/lib/lrama.rb13
-rw-r--r--tool/lrama/lib/lrama/bitmap.rb29
-rw-r--r--tool/lrama/lib/lrama/command.rb144
-rw-r--r--tool/lrama/lib/lrama/context.rb511
-rw-r--r--tool/lrama/lib/lrama/digraph.rb53
-rw-r--r--tool/lrama/lib/lrama/grammar.rb850
-rw-r--r--tool/lrama/lib/lrama/lexer.rb349
-rw-r--r--tool/lrama/lib/lrama/output.rb370
-rw-r--r--tool/lrama/lib/lrama/parser.rb321
-rw-r--r--tool/lrama/lib/lrama/report.rb47
-rw-r--r--tool/lrama/lib/lrama/states.rb832
-rw-r--r--tool/lrama/lib/lrama/states_reporter.rb310
-rw-r--r--tool/lrama/lib/lrama/version.rb3
-rw-r--r--tool/lrama/lib/lrama/warning.rb25
-rw-r--r--tool/lrama/template/bison/yacc.c1743
-rw-r--r--tool/lrama/template/bison/yacc.h112
-rwxr-xr-xtool/make-snapshot2
-rw-r--r--win32/Makefile.sub2
38 files changed, 5749 insertions, 30 deletions
diff --git a/.github/workflows/baseruby.yml b/.github/workflows/baseruby.yml
index cc8727bc4e..7a1ef841b8 100644
--- a/.github/workflows/baseruby.yml
+++ b/.github/workflows/baseruby.yml
@@ -56,7 +56,7 @@ jobs:
ruby-version: ${{ matrix.ruby }}
bundler: none
- run: echo "GNUMAKEFLAGS=-j$((1 + $(nproc --all)))" >> $GITHUB_ENV
- - run: sudo apt-get install build-essential autoconf bison libyaml-dev
+ - run: sudo apt-get install build-essential autoconf libyaml-dev
- run: ./autogen.sh
- run: ./configure --disable-install-doc
- run: make common-srcs
diff --git a/.github/workflows/bundled_gems.yml b/.github/workflows/bundled_gems.yml
index 3396e562c0..c871388f93 100644
--- a/.github/workflows/bundled_gems.yml
+++ b/.github/workflows/bundled_gems.yml
@@ -76,7 +76,7 @@ jobs:
run: |
set -x
sudo apt-get update -q || :
- sudo apt-get install --no-install-recommends -q -y build-essential libssl-dev libyaml-dev libreadline6-dev zlib1g-dev libncurses5-dev libffi-dev bison autoconf ruby
+ sudo apt-get install --no-install-recommends -q -y build-essential libssl-dev libyaml-dev libreadline6-dev zlib1g-dev libncurses5-dev libffi-dev autoconf ruby
if: ${{ steps.diff.outcome == 'failure' }}
- name: Build
diff --git a/.github/workflows/check_dependencies.yml b/.github/workflows/check_dependencies.yml
index cbd88a3e0d..642c3255ce 100644
--- a/.github/workflows/check_dependencies.yml
+++ b/.github/workflows/check_dependencies.yml
@@ -42,7 +42,7 @@ jobs:
run: |
set -x
sudo apt-get update -q || :
- sudo apt-get install --no-install-recommends -q -y build-essential libssl-dev libyaml-dev libreadline6-dev zlib1g-dev libncurses5-dev libffi-dev bison autoconf ruby
+ sudo apt-get install --no-install-recommends -q -y build-essential libssl-dev libyaml-dev libreadline6-dev zlib1g-dev libncurses5-dev libffi-dev autoconf ruby
if: ${{ contains(matrix.os, 'ubuntu') }}
- name: Install libraries
run: |
diff --git a/.github/workflows/codeql-analysis.yml b/.github/workflows/codeql-analysis.yml
index 782424b0d6..c299b9bc62 100644
--- a/.github/workflows/codeql-analysis.yml
+++ b/.github/workflows/codeql-analysis.yml
@@ -51,7 +51,7 @@ jobs:
run: |
set -x
sudo apt-get update -q || :
- sudo apt-get install --no-install-recommends -q -y build-essential libssl-dev libyaml-dev libreadline6-dev zlib1g-dev libncurses5-dev libffi-dev bison autoconf ruby
+ sudo apt-get install --no-install-recommends -q -y build-essential libssl-dev libyaml-dev libreadline6-dev zlib1g-dev libncurses5-dev libffi-dev autoconf ruby
- name: Checkout repository
uses: actions/checkout@8e5e7e5ab8b370d6c329ec480221332ada57f0ab # v3.5.2
diff --git a/.github/workflows/macos.yml b/.github/workflows/macos.yml
index 4228e0d4d5..908a3f5b61 100644
--- a/.github/workflows/macos.yml
+++ b/.github/workflows/macos.yml
@@ -59,12 +59,11 @@ jobs:
- name: Install libraries
run: |
brew upgrade
- brew install gmp libffi openssl@1.1 zlib autoconf automake libtool readline bison
+ brew install gmp libffi openssl@1.1 zlib autoconf automake libtool readline
working-directory: src
- name: Set ENV
run: |
echo "MAKEFLAGS=-j$((1 + $(sysctl -n hw.activecpu)))" >> $GITHUB_ENV
- echo "PATH="/usr/local/opt/bison/bin:$PATH"" >> $GITHUB_ENV
for lib in openssl@1.1 readline; do
CONFIGURE_ARGS="${CONFIGURE_ARGS:+$CONFIGURE_ARGS }--with-${lib%@*}-dir=$(brew --prefix $lib)"
done
diff --git a/.github/workflows/mingw.yml b/.github/workflows/mingw.yml
index 8e0a006d3c..e69da91484 100644
--- a/.github/workflows/mingw.yml
+++ b/.github/workflows/mingw.yml
@@ -85,7 +85,7 @@ jobs:
mv /c/Windows/System32/libcrypto-1_1-x64.dll /c/Windows/System32/libcrypto-1_1-x64.dll_
mv /c/Windows/System32/libssl-1_1-x64.dll /c/Windows/System32/libssl-1_1-x64.dll_
result=true
- for e in gcc.exe ragel.exe make.exe bison.exe libcrypto-1_1-x64.dll libssl-1_1-x64.dll; do
+ for e in gcc.exe ragel.exe make.exe libcrypto-1_1-x64.dll libssl-1_1-x64.dll; do
echo '##['group']'$'\033[93m'$e$'\033[m'
where $e || result=false
echo '##['endgroup']'
@@ -96,7 +96,7 @@ jobs:
run: |
# show version
result=true
- for e in gcc ragel make bison "openssl version"; do
+ for e in gcc ragel make "openssl version"; do
case "$e" in *" "*) ;; *) e="$e --version";; esac
echo '##['group']'$'\033[93m'$e$'\033[m'
$e || result=false
diff --git a/.github/workflows/rjit-bindgen.yml b/.github/workflows/rjit-bindgen.yml
index dafbc367f4..86ec4215bd 100644
--- a/.github/workflows/rjit-bindgen.yml
+++ b/.github/workflows/rjit-bindgen.yml
@@ -53,7 +53,7 @@ jobs:
libssl-dev libyaml-dev libreadline6-dev \
zlib1g-dev libncurses5-dev libffi-dev \
libclang1-10 \
- bison autoconf
+ autoconf
sudo apt-get install -q -y pkg-config || :
- name: Set up Ruby
uses: ruby/setup-ruby@d2b39ad0b52eca07d23f3aa14fdf2a3fcc1f411c # v1.148.0
diff --git a/.github/workflows/rjit.yml b/.github/workflows/rjit.yml
index dce7b78631..f7dc9ad0ee 100644
--- a/.github/workflows/rjit.yml
+++ b/.github/workflows/rjit.yml
@@ -65,7 +65,7 @@ jobs:
${arch:+cross}build-essential${arch/:/-} \
libssl-dev${arch} libyaml-dev${arch} libreadline6-dev${arch} \
zlib1g-dev${arch} libncurses5-dev${arch} libffi-dev${arch} \
- bison autoconf ruby libcapstone-dev
+ autoconf ruby libcapstone-dev
sudo apt-get install -q -y pkg-config${arch} || :
- name: git config
run: |
diff --git a/.github/workflows/ubuntu.yml b/.github/workflows/ubuntu.yml
index 3deabea9e9..d8a557ab4f 100644
--- a/.github/workflows/ubuntu.yml
+++ b/.github/workflows/ubuntu.yml
@@ -70,7 +70,7 @@ jobs:
${arch:+cross}build-essential${arch/:/-} \
libssl-dev${arch} libyaml-dev${arch} libreadline6-dev${arch} \
zlib1g-dev${arch} libncurses5-dev${arch} libffi-dev${arch} \
- bison autoconf ruby
+ autoconf ruby
sudo apt-get install -q -y pkg-config${arch} || :
- name: git config
run: |
diff --git a/.github/workflows/wasm.yml b/.github/workflows/wasm.yml
index 3a7bd5e8be..9e123889d6 100644
--- a/.github/workflows/wasm.yml
+++ b/.github/workflows/wasm.yml
@@ -66,7 +66,7 @@ jobs:
run: |
set -ex
sudo apt-get update -q || :
- sudo apt-get install --no-install-recommends -q -y ruby bison make autoconf git wget
+ sudo apt-get install --no-install-recommends -q -y ruby make autoconf git wget
wasi_sdk_deb="wasi-sdk_${WASI_SDK_VERSION_MAJOR}.${WASI_SDK_VERSION_MINOR}_amd64.deb"
wget "https://github.com/WebAssembly/wasi-sdk/releases/download/wasi-sdk-${WASI_SDK_VERSION_MAJOR}/${wasi_sdk_deb}"
diff --git a/.github/workflows/windows.yml b/.github/workflows/windows.yml
index 311db28744..75f026074f 100644
--- a/.github/workflows/windows.yml
+++ b/.github/workflows/windows.yml
@@ -79,7 +79,6 @@ jobs:
run: |
iex "& {$(irm get.scoop.sh)} -RunAsAdmin"
Join-Path (Resolve-Path ~).Path "scoop\shims" >> $Env:GITHUB_PATH
- scoop install winflexbison
shell: pwsh
- name: git config
run: |
diff --git a/.github/workflows/yjit-ubuntu.yml b/.github/workflows/yjit-ubuntu.yml
index 710171723a..9cb5c87120 100644
--- a/.github/workflows/yjit-ubuntu.yml
+++ b/.github/workflows/yjit-ubuntu.yml
@@ -103,7 +103,7 @@ jobs:
run: |
set -x
sudo apt-get update -q || :
- sudo apt-get install --no-install-recommends -q -y build-essential libssl-dev libyaml-dev libreadline6-dev zlib1g-dev libncurses5-dev libffi-dev bison autoconf ruby
+ sudo apt-get install --no-install-recommends -q -y build-essential libssl-dev libyaml-dev libreadline6-dev zlib1g-dev libncurses5-dev libffi-dev autoconf ruby
- name: Install Rust
if: ${{ matrix.rust_version }}
run: rustup install ${{ matrix.rust_version }} --profile minimal
diff --git a/common.mk b/common.mk
index 0c9f923633..d0b674e32c 100644
--- a/common.mk
+++ b/common.mk
@@ -298,7 +298,8 @@ configure-ext: $(EXTS_MK)
build-ext: $(EXTS_MK)
$(Q)$(MAKE) -f $(EXTS_MK) $(mflags) libdir="$(libdir)" LIBRUBY_EXTS=$(LIBRUBY_EXTS) \
- EXTENCS="$(ENCOBJS)" MINIRUBY="$(MINIRUBY)" UPDATE_LIBRARIES=no $(EXTSTATIC)
+ EXTENCS="$(ENCOBJS)" BASERUBY="$(BASERUBY)" MINIRUBY="$(MINIRUBY)" \
+ UPDATE_LIBRARIES=no $(EXTSTATIC)
$(Q)$(MAKE) $(EXTS_NOTE)
exts-note: $(EXTS_MK)
@@ -1208,8 +1209,8 @@ $(srcdir)/ext/ripper/ripper.c: $(srcdir)/ext/ripper/tools/preproc.rb $(srcdir)/p
$(Q) $(CHDIR) $(@D) && \
$(CAT_DEPEND) depend | \
$(exec) $(MAKE) -f - $(mflags) \
- Q=$(Q) ECHO=$(ECHO) RM="$(RM1)" BISON="$(YACC)" top_srcdir=../.. srcdir=. VPATH=../.. \
- RUBY="$(BASERUBY)" PATH_SEPARATOR="$(PATH_SEPARATOR)" LANG=C
+ Q=$(Q) ECHO=$(ECHO) RM="$(RM1)" top_srcdir=../.. srcdir=. VPATH=../.. \
+ RUBY="$(BASERUBY)" BASERUBY="$(BASERUBY)" PATH_SEPARATOR="$(PATH_SEPARATOR)" LANG=C
$(srcdir)/ext/json/parser/parser.c: $(srcdir)/ext/json/parser/parser.rl $(srcdir)/ext/json/parser/prereq.mk
$(ECHO) generating $@
diff --git a/defs/gmake.mk b/defs/gmake.mk
index 1d81da8bf6..2c03022434 100644
--- a/defs/gmake.mk
+++ b/defs/gmake.mk
@@ -1,6 +1,7 @@
# -*- mode: makefile-gmake; indent-tabs-mode: t -*-
reconfig config.status: export MAKE:=$(MAKE)
+export BASERUBY:=$(BASERUBY)
override gnumake_recursive := $(if $(findstring n,$(firstword $(MFLAGS))),,+)
override mflags := $(filter-out -j%,$(MFLAGS))
MSPECOPT += $(if $(filter -j%,$(MFLAGS)),-j)
diff --git a/doc/contributing/building_ruby.md b/doc/contributing/building_ruby.md
index 8e6c083183..d4cedbcb69 100644
--- a/doc/contributing/building_ruby.md
+++ b/doc/contributing/building_ruby.md
@@ -15,7 +15,6 @@
If you want to build from the git repository, you will also need:
* autoconf - 2.67 or later
- * bison - 3.0 or later
* gperf - 3.1 or later
* Usually unneeded; only if you edit some source files using gperf
* ruby - 2.5 or later
diff --git a/doc/windows.md b/doc/windows.md
index 8e465e5eaf..8159b25861 100644
--- a/doc/windows.md
+++ b/doc/windows.md
@@ -19,7 +19,7 @@ Ruby core development can be done either in Windows `cmd` like:
```
ridk enable ucrt64
-pacman -S --needed bison %MINGW_PACKAGE_PREFIX%-openssl %MINGW_PACKAGE_PREFIX%-libyaml
+pacman -S --needed %MINGW_PACKAGE_PREFIX%-openssl %MINGW_PACKAGE_PREFIX%-libyaml
cd c:\
mkdir work
@@ -38,7 +38,7 @@ or in MSYS2 `bash` like:
ridk enable ucrt64
bash
-pacman -S --needed bison $MINGW_PACKAGE_PREFIX-openssl $MINGW_PACKAGE_PREFIX-libyaml
+pacman -S --needed $MINGW_PACKAGE_PREFIX-openssl $MINGW_PACKAGE_PREFIX-libyaml
cd /c/
mkdir work
@@ -78,7 +78,6 @@ make
* dumpbin
4. If you want to build from GIT source, following commands are required.
- * bison
* patch
* sed
* ruby 2.0 or later
@@ -86,7 +85,7 @@ make
You can use [scoop](https://scoop.sh/) to install them like:
```
- scoop install git ruby winflexbison sed patch
+ scoop install git ruby sed patch
```
5. You need to install required libraries using [vcpkg](https://vcpkg.io/) like:
diff --git a/ext/ripper/depend b/ext/ripper/depend
index 84deba62ed..9aba267533 100644
--- a/ext/ripper/depend
+++ b/ext/ripper/depend
@@ -1,6 +1,7 @@
GEN = $(srcdir)/tools/generate.rb
SRC1 = $(top_srcdir)/parse.y
SRC2 = $(srcdir)/eventids2.c
+BISON = $(BASERUBY) $(top_srcdir)/tool/lrama/exe/lrama
.SUFFIXES: .y
@@ -10,6 +11,7 @@ ripper.o: ripper.c
.y.c:
$(ECHO) compiling compiler $<
+ $(ECHO) $(BISON)
$(Q) $(BISON) -t -v -oy.tab.c $<
$(Q) sed -e "/^#/s!y\.tab\.c!$@!" -f $(top_srcdir)/tool/ytab.sed y.tab.c > $@
@$(RM) y.tab.c
diff --git a/ext/ripper/extconf.rb b/ext/ripper/extconf.rb
index 65cb5030d3..bff5d429c3 100644
--- a/ext/ripper/extconf.rb
+++ b/ext/ripper/extconf.rb
@@ -7,11 +7,11 @@ require 'rbconfig'
def main
yacc = ENV["YACC"] || "bison"
- unless find_executable(yacc)
- unless File.exist?('ripper.c') or File.exist?("#{$srcdir}/ripper.c")
- raise 'missing bison; abort'
- end
- end
+ # unless find_executable(yacc)
+ # unless File.exist?('ripper.c') or File.exist?("#{$srcdir}/ripper.c")
+ # raise 'missing bison; abort'
+ # end
+ # end
$objs = %w(ripper.o)
$distcleanfiles.concat %w(ripper.y ripper.c eventids1.c eventids2table.c)
$cleanfiles.concat %w(ripper.E ripper.output y.output .eventids2-check)
diff --git a/template/Makefile.in b/template/Makefile.in
index d61f874a2d..76648bb661 100644
--- a/template/Makefile.in
+++ b/template/Makefile.in
@@ -29,7 +29,7 @@ CPP = @CPP@
LD = @LD@
RUSTC = @RUSTC@
CARGO = @CARGO@
-YACC = bison
+YACC = $(BASERUBY) $(tooldir)/lrama/exe/lrama
PURIFY =
AUTOCONF = autoconf
CONFIGURE = @CONFIGURE@
diff --git a/tool/lrama/exe/lrama b/tool/lrama/exe/lrama
new file mode 100755
index 0000000000..5c61e1a684
--- /dev/null
+++ b/tool/lrama/exe/lrama
@@ -0,0 +1,7 @@
+#!/usr/bin/env ruby
+
+
+$LOAD_PATH << File.join(__dir__, "../lib")
+require "lrama"
+
+Lrama::Command.new.run(ARGV.dup)
diff --git a/tool/lrama/lib/lrama.rb b/tool/lrama/lib/lrama.rb
new file mode 100644
index 0000000000..1973cc6646
--- /dev/null
+++ b/tool/lrama/lib/lrama.rb
@@ -0,0 +1,13 @@
+require "lrama/bitmap"
+require "lrama/command"
+require "lrama/context"
+require "lrama/digraph"
+require "lrama/grammar"
+require "lrama/lexer"
+require "lrama/output"
+require "lrama/parser"
+require "lrama/report"
+require "lrama/states"
+require "lrama/states_reporter"
+require "lrama/version"
+require "lrama/warning"
diff --git a/tool/lrama/lib/lrama/bitmap.rb b/tool/lrama/lib/lrama/bitmap.rb
new file mode 100644
index 0000000000..8349a23c34
--- /dev/null
+++ b/tool/lrama/lib/lrama/bitmap.rb
@@ -0,0 +1,29 @@
+module Lrama
+ module Bitmap
+ def self.from_array(ary)
+ bit = 0
+
+ ary.each do |int|
+ bit |= (1 << int)
+ end
+
+ bit
+ end
+
+ def self.to_array(int)
+ a = []
+ i = 0
+
+ while int > 0 do
+ if int & 1 == 1
+ a << i
+ end
+
+ i += 1
+ int >>= 1
+ end
+
+ a
+ end
+ end
+end
diff --git a/tool/lrama/lib/lrama/command.rb b/tool/lrama/lib/lrama/command.rb
new file mode 100644
index 0000000000..71369de8ef
--- /dev/null
+++ b/tool/lrama/lib/lrama/command.rb
@@ -0,0 +1,144 @@
+require 'optparse'
+
+module Lrama
+ class Command
+ def run(argv)
+ opt = OptionParser.new
+
+ # opt.on('-h') {|v| p v }
+ opt.on('-V', '--version') {|v| puts Lrama::VERSION ; exit 0 }
+
+ # Tuning the Parser
+ skeleton = "bison/yacc.c"
+
+ opt.on('-S', '--skeleton=FILE') {|v| skeleton = v }
+ opt.on('-t') { } # Do nothing
+
+ # Output Files:
+ header = false
+ header_file = nil
+ report = []
+ report_file = nil
+ outfile = "y.tab.c"
+
+ opt.on('-h', '--header=[FILE]') {|v| header = true; header_file = v }
+ opt.on('-d') { header = true }
+ opt.on('-r', '--report=THINGS') {|v| report = v.split(',') }
+ opt.on('--report-file=FILE') {|v| report_file = v }
+ opt.on('-v') { } # Do nothing
+ opt.on('-o', '--output=FILE') {|v| outfile = v }
+
+ # Hidden
+ trace = []
+ opt.on('--trace=THINGS') {|v| trace = v.split(',') }
+
+ # Error Recovery
+ error_recovery = false
+ opt.on('-e') {|v| error_recovery = true }
+
+ opt.parse!(argv)
+
+ trace_opts = validate_trace(trace)
+ report_opts = validate_report(report)
+
+ grammar_file = argv.shift
+
+ if !report.empty? && report_file.nil? && grammar_file
+ report_file = File.dirname(grammar_file) + "/" + File.basename(grammar_file, ".*") + ".output"
+ end
+
+ if !header_file && header
+ case
+ when outfile
+ header_file = File.dirname(outfile) + "/" + File.basename(outfile, ".*") + ".h"
+ when grammar_file
+ header_file = File.dirname(grammar_file) + "/" + File.basename(grammar_file, ".*") + ".h"
+ end
+ end
+
+ if !grammar_file
+ puts "File should be specified\n"
+ exit 1
+ end
+
+ Report::Duration.enable if trace_opts[:time]
+
+ warning = Lrama::Warning.new
+ y = File.read(grammar_file)
+ grammar = Lrama::Parser.new(y).parse
+ states = Lrama::States.new(grammar, warning, trace_state: (trace_opts[:automaton] || trace_opts[:closure]))
+ states.compute
+ context = Lrama::Context.new(states)
+
+ if report_file
+ reporter = Lrama::StatesReporter.new(states)
+ File.open(report_file, "w+") do |f|
+ reporter.report(f, **report_opts)
+ end
+ end
+
+ File.open(outfile, "w+") do |f|
+ Lrama::Output.new(
+ out: f,
+ output_file_path: outfile,
+ template_name: skeleton,
+ grammar_file_path: grammar_file,
+ header_file_path: header_file,
+ context: context,
+ grammar: grammar,
+ ).render
+ end
+
+ if warning.has_error?
+ exit 1
+ end
+ end
+
+ private
+
+ def validate_report(report)
+ bison_list = %w[states itemsets lookaheads solved counterexamples cex all none]
+ others = %w[verbose]
+ list = bison_list + others
+ not_supported = %w[counterexamples cex none]
+ h = { grammar: true }
+
+ report.each do |r|
+ if list.include?(r) && !not_supported.include?(r)
+ h[r.to_sym] = true
+ else
+ raise "Invalid report option \"#{r}\"."
+ end
+ end
+
+ if h[:all]
+ (bison_list - not_supported).each do |r|
+ h[r.to_sym] = true
+ end
+
+ h.delete(:all)
+ end
+
+ return h
+ end
+
+ def validate_trace(trace)
+ list = %w[
+ none locations scan parse automaton bitsets
+ closure grammar resource sets muscles tools
+ m4-early m4 skeleton time ielr cex all
+ ]
+ h = {}
+
+ trace.each do |t|
+ if list.include?(t)
+ h[t.to_sym] = true
+ else
+ raise "Invalid trace option \"#{t}\"."
+ end
+ end
+
+ return h
+ end
+ end
+end
diff --git a/tool/lrama/lib/lrama/context.rb b/tool/lrama/lib/lrama/context.rb
new file mode 100644
index 0000000000..9086470011
--- /dev/null
+++ b/tool/lrama/lib/lrama/context.rb
@@ -0,0 +1,511 @@
+require "lrama/report"
+
+module Lrama
+ # This is passed to a template
+ class Context
+ include Report::Duration
+
+ ErrorActionNumber = -Float::INFINITY
+ BaseMin = -Float::INFINITY
+
+ # TODO: It might be better to pass `states` to Output directly?
+ attr_reader :states
+
+ def initialize(states)
+ @states = states
+ @yydefact = nil
+ @yydefgoto = nil
+ # Array of array
+ @_actions = []
+
+ compute_tables
+ end
+
+ # enum yytokentype
+ def yytokentype
+ @states.terms.reject do |term|
+ 0 < term.token_id && term.token_id < 128
+ end.map do |term|
+ [term.id.s_value, term.token_id, term.display_name]
+ end.unshift(["YYEMPTY", -2, nil])
+ end
+
+ # enum yysymbol_kind_t
+ def yysymbol_kind_t
+ @states.symbols.map do |sym|
+ [sym.enum_name, sym.number, sym.comment]
+ end.unshift(["YYSYMBOL_YYEMPTY", -2, nil])
+ end
+
+ # State number of final (accepted) state
+ def yyfinal
+ @states.states.find do |state|
+ state.items.find do |item|
+ item.rule.lhs.id.s_value == "$accept" && item.end_of_rule?
+ end
+ end.id
+ end
+
+ def yylast
+ @yylast
+ end
+
+ # Number of terms
+ def yyntokens
+ @states.terms.count
+ end
+
+ # Number of nterms
+ def yynnts
+ @states.nterms.count
+ end
+
+ # Number of rules
+ def yynrules
+ @states.rules.count
+ end
+
+ # Number of states
+ def yynstates
+ @states.states.count
+ end
+
+ # Last token number
+ def yymaxutok
+ @states.terms.map(&:token_id).max
+ end
+
+ # YYTRANSLATE
+ #
+ # yytranslate is a mapping from token id to symbol number
+ def yytranslate
+ # 2 is YYSYMBOL_YYUNDEF
+ a = Array.new(yymaxutok, 2)
+
+ @states.terms.each do |term|
+ a[term.token_id] = term.number
+ end
+
+ return a
+ end
+
+ # Mapping from rule number to line number of the rule is defined.
+ # Dummy rule is appended as the first element whose value is 0
+ # because 0 means error in yydefact.
+ def yyrline
+ a = [0]
+
+ @states.rules.each do |rule|
+ a << rule.lineno
+ end
+
+ return a
+ end
+
+ # Mapping from symbol number to its name
+ def yytname
+ @states.symbols.sort_by(&:number).map do |sym|
+ sym.display_name
+ end
+ end
+
+ def yypact_ninf
+ @yypact_ninf
+ end
+
+ def yytable_ninf
+ @yytable_ninf
+ end
+
+ def yypact
+ @base[0...yynstates]
+ end
+
+ def yydefact
+ @yydefact
+ end
+
+ def yypgoto
+ @base[yynstates..-1]
+ end
+
+ def yydefgoto
+ @yydefgoto
+ end
+
+ def yytable
+ @table
+ end
+
+ def yycheck
+ @check
+ end
+
+ def yystos
+ @states.states.map do |state|
+ state.accessing_symbol.number
+ end
+ end
+
+ # Mapping from rule number to symbol number of LHS.
+ # Dummy rule is appended as the first element whose value is 0
+ # because 0 means error in yydefact.
+ def yyr1
+ a = [0]
+
+ @states.rules.each do |rule|
+ a << rule.lhs.number
+ end
+
+ return a
+ end
+
+ # Mapping from rule number to lenght of RHS.
+ # Dummy rule is appended as the first element whose value is 0
+ # because 0 means error in yydefact.
+ def yyr2
+ a = [0]
+
+ @states.rules.each do |rule|
+ a << rule.rhs.count
+ end
+
+ return a
+ end
+
+ private
+
+ # Compute these
+ #
+ # See also: "src/tables.c" of Bison.
+ #
+ # * yydefact
+ # * yydefgoto
+ # * yypact and yypgoto
+ # * yytable
+ # * yycheck
+ # * yypact_ninf
+ # * yytable_ninf
+ def compute_tables
+ report_duration(:compute_yydefact) { compute_yydefact }
+ report_duration(:compute_yydefgoto) { compute_yydefgoto }
+ report_duration(:sort_actions) { sort_actions }
+ # debug_sorted_actions
+ report_duration(:compute_packed_table) { compute_packed_table }
+ end
+
+ def vectors_count
+ @states.states.count + @states.nterms.count
+ end
+
+ # In compressed table, rule 0 is appended as an error case
+ # and reduce is represented as minus number.
+ def rule_id_to_action_number(rule_id)
+ (rule_id + 1) * -1
+ end
+
+ # Symbol number is assinged to term first then nterm.
+ # This method calculates sequence_number for nterm.
+ def nterm_number_to_sequence_number(nterm_number)
+ nterm_number - @states.terms.count
+ end
+
+ # Vector is states + nterms
+ def nterm_number_to_vector_number(nterm_number)
+ @states.states.count + (nterm_number - @states.terms.count)
+ end
+
+ def compute_yydefact
+ # Default action (shift/reduce/error) for each state.
+ # Index is state id, value is `rule id + 1` of a default reduction.
+ @yydefact = Array.new(@states.states.count, 0)
+
+ @states.states.each do |state|
+ # Action number means
+ #
+ # * number = 0, default action
+ # * number = -Float::INFINITY, error by %nonassoc
+ # * number > 0, shift then move to state "number"
+ # * number < 0, reduce by "-number" rule. Rule "number" is already added by 1.
+ actions = Array.new(@states.terms.count, 0)
+
+ if state.reduces.map(&:selected_look_ahead).any? {|la| !la.empty? }
+ # Iterate reduces with reverse order so that first rule is used.
+ state.reduces.reverse.each do |reduce|
+ reduce.look_ahead.each do |term|
+ actions[term.number] = rule_id_to_action_number(reduce.rule.id)
+ end
+ end
+ end
+
+ # Shift is selected when S/R conflict exists.
+ state.selected_term_transitions.each do |shift, next_state|
+ actions[shift.next_sym.number] = next_state.id
+ end
+
+ state.resolved_conflicts.select do |conflict|
+ conflict.which == :error
+ end.each do |conflict|
+ actions[conflict.symbol.number] = ErrorActionNumber
+ end
+
+ # If default_reduction_rule, replase default_reduction_rule in
+ # actions with zero.
+ if state.default_reduction_rule
+ actions.map! do |e|
+ if e == rule_id_to_action_number(state.default_reduction_rule.id)
+ 0
+ else
+ e
+ end
+ end
+ end
+
+ # If no default_reduction_rule, default behavior is an
+ # error then replase ErrorActionNumber with zero.
+ if !state.default_reduction_rule
+ actions.map! do |e|
+ if e == ErrorActionNumber
+ 0
+ else
+ e
+ end
+ end
+ end
+
+ s = actions.each_with_index.map do |n, i|
+ [i, n]
+ end.select do |i, n|
+ # Remove default_reduction_rule entries
+ n != 0
+ end
+
+ if s.count != 0
+ # Entry of @_actions is an array of
+ #
+ # * State id
+ # * Array of tuple, [from, to] where from is term number and to is action.
+ # * The number of "Array of tuple" used by sort_actions
+ # * "width" used by sort_actions
+ @_actions << [state.id, s, s.count, s.last[0] - s.first[0] + 1]
+ end
+
+ @yydefact[state.id] = state.default_reduction_rule ? state.default_reduction_rule.id + 1 : 0
+ end
+ end
+
+ def compute_yydefgoto
+ # Default GOTO (nterm transition) for each nterm.
+ # Index is sequence number of nterm, value is state id
+ # of a default nterm transition destination.
+ @yydefgoto = Array.new(@states.nterms.count, 0)
+ h = {}
+ # Mapping from nterm to next_states
+ nterm_to_next_states = {}
+ terms_count = @states.terms.count
+
+ @states.states.each do |state|
+ state.nterm_transitions.each do |shift, next_state|
+ key = shift.next_sym
+ nterm_to_next_states[key] ||= []
+ nterm_to_next_states[key] << [state, next_state] # [from_state, to_state]
+ end
+ end
+
+ @states.nterms.each do |nterm|
+ if !(states = nterm_to_next_states[nterm])
+ default_goto = 0
+ not_default_gotos = []
+ else
+ default_state = states.map(&:last).group_by {|s| s }.max_by {|_, v| v.count }.first
+ default_goto = default_state.id
+ not_default_gotos = []
+ states.each do |from_state, to_state|
+ next if to_state.id == default_goto
+ not_default_gotos << [from_state.id, to_state.id]
+ end
+ end
+
+ k = nterm_number_to_sequence_number(nterm.number)
+ @yydefgoto[k] = default_goto
+
+ if not_default_gotos.count != 0
+ v = nterm_number_to_vector_number(nterm.number)
+
+ # Entry of @_actions is an array of
+ #
+ # * Nterm number as vector number
+ # * Array of tuple, [from, to] where from is state number and to is state number.
+ # * The number of "Array of tuple" used by sort_actions
+ # * "width" used by sort_actions
+ @_actions << [v, not_default_gotos, not_default_gotos.count, not_default_gotos.last[0] - not_default_gotos.first[0] + 1]
+ end
+ end
+ end
+
+ def sort_actions
+ # This is not same with #sort_actions
+ #
+ # @sorted_actions = @_actions.sort_by do |_, _, count, width|
+ # [-width, -count]
+ # end
+
+ @sorted_actions = []
+
+ @_actions.each do |action|
+ if @sorted_actions.empty?
+ @sorted_actions << action
+ next
+ end
+
+ j = @sorted_actions.count - 1
+ state_id, froms_and_tos, count, width = action
+
+ while (j >= 0) do
+ case
+ when @sorted_actions[j][3] < width
+ j -= 1
+ when @sorted_actions[j][3] == width && @sorted_actions[j][2] < count
+ j -= 1
+ else
+ break
+ end
+ end
+
+ @sorted_actions.insert(j + 1, action)
+ end
+ end
+
+ def debug_sorted_actions
+ ary = Array.new
+ @sorted_actions.each do |state_id, froms_and_tos, count, width|
+ ary[state_id] = [state_id, froms_and_tos, count, width]
+ end
+
+ print sprintf("table_print:\n\n")
+
+ print sprintf("order [\n")
+ vectors_count.times do |i|
+ print sprintf("%d, ", @sorted_actions[i] ? @sorted_actions[i][0] : 0)
+ print "\n" if i % 10 == 9
+ end
+ print sprintf("]\n\n")
+
+
+ print sprintf("width [\n")
+ vectors_count.times do |i|
+ print sprintf("%d, ", ary[i] ? ary[i][3] : 0)
+ print "\n" if i % 10 == 9
+ end
+ print sprintf("]\n\n")
+
+
+ print sprintf("tally [\n")
+ vectors_count.times do |i|
+ print sprintf("%d, ", ary[i] ? ary[i][2] : 0)
+ print "\n" if i % 10 == 9
+ end
+ print sprintf("]\n\n")
+ end
+
+ def compute_packed_table
+ # yypact and yypgoto
+ @base = Array.new(vectors_count, BaseMin)
+ # yytable
+ @table = []
+ # yycheck
+ @check = []
+ # Key is froms_and_tos, value is index position
+ pushed = {}
+ userd_res = {}
+ lowzero = 0
+ high = 0
+
+ @sorted_actions.each do |state_id, froms_and_tos, _, _|
+ if (res = pushed[froms_and_tos])
+ @base[state_id] = res
+ next
+ end
+
+ res = lowzero - froms_and_tos.first[0]
+
+ while true do
+ ok = true
+
+ froms_and_tos.each do |from, to|
+ loc = res + from
+
+ if @table[loc]
+ # If the cell of table is set, can not use the cell.
+ ok = false
+ break
+ end
+ end
+
+ if ok && userd_res[res]
+ ok = false
+ end
+
+ if ok
+ break
+ else
+ res += 1
+ end
+ end
+
+ loc = 0
+
+ froms_and_tos.each do |from, to|
+ loc = res + from
+
+ @table[loc] = to
+ @check[loc] = from
+ end
+
+ while (@table[lowzero]) do
+ lowzero += 1
+ end
+
+ high = loc if high < loc
+
+ @base[state_id] = res
+ pushed[froms_and_tos] = res
+ userd_res[res] = true
+ end
+
+ @yylast = high
+
+ # replace_ninf
+ @yypact_ninf = (@base.select {|i| i != BaseMin } + [0]).min - 1
+ @base.map! do |i|
+ case i
+ when BaseMin
+ @yypact_ninf
+ else
+ i
+ end
+ end
+
+ @yytable_ninf = (@table.compact.select {|i| i != ErrorActionNumber } + [0]).min - 1
+ @table.map! do |i|
+ case i
+ when nil
+ 0
+ when ErrorActionNumber
+ @yytable_ninf
+ else
+ i
+ end
+ end
+
+ @check.map! do |i|
+ case i
+ when nil
+ -1
+ else
+ i
+ end
+ end
+ end
+ end
+end
diff --git a/tool/lrama/lib/lrama/digraph.rb b/tool/lrama/lib/lrama/digraph.rb
new file mode 100644
index 0000000000..28f26781b1
--- /dev/null
+++ b/tool/lrama/lib/lrama/digraph.rb
@@ -0,0 +1,53 @@
+module Lrama
+ # Algorithm Digraph of https://dl.acm.org/doi/pdf/10.1145/69622.357187 (P. 625)
+ class Digraph
+ def initialize(sets, relation, base_function)
+ # X in the paper
+ @sets = sets
+ # R in the paper
+ @relation = relation
+ # F' in the paper
+ @base_function = base_function
+ # S in the paper
+ @stack = []
+ # N in the paper
+ @h = Hash.new(0)
+ # F in the paper
+ @result = {}
+ end
+
+ def compute
+ @sets.each do |x|
+ next if @h[x] != 0
+ traverse(x)
+ end
+
+ return @result
+ end
+
+ private
+
+ def traverse(x)
+ @stack.push(x)
+ d = @stack.count
+ @h[x] = d
+ @result[x] = @base_function[x] # F x = F' x
+
+ @relation[x] && @relation[x].each do |y|
+ traverse(y) if @h[y] == 0
+ @h[x] = [@h[x], @h[y]].min
+ @result[x] |= @result[y] # F x = F x + F y
+ end
+
+ if @h[x] == d
+ while true do
+ z = @stack.pop
+ @h[z] = Float::INFINITY
+ @result[z] = @result[x] # F (Top of S) = F x
+
+ break if z == x
+ end
+ end
+ end
+ end
+end
diff --git a/tool/lrama/lib/lrama/grammar.rb b/tool/lrama/lib/lrama/grammar.rb
new file mode 100644
index 0000000000..8ca75cb60b
--- /dev/null
+++ b/tool/lrama/lib/lrama/grammar.rb
@@ -0,0 +1,850 @@
+require "forwardable"
+require "lrama/lexer"
+
+module Lrama
+ Rule = Struct.new(:id, :lhs, :rhs, :code, :nullable, :precedence_sym, :lineno, keyword_init: true) do
+ # TODO: Change this to display_name
+ def to_s
+ l = lhs.id.s_value
+ r = rhs.empty? ? "ε" : rhs.map {|r| r.id.s_value }.join(", ")
+
+ "#{l} -> #{r}"
+ end
+
+ # Used by #user_actions
+ def as_comment
+ l = lhs.id.s_value
+ r = rhs.empty? ? "%empty" : rhs.map {|r| r.display_name }.join(" ")
+
+ "#{l}: #{r}"
+ end
+
+ def precedence
+ precedence_sym && precedence_sym.precedence
+ end
+
+ def initial_rule?
+ id == 0
+ end
+
+ def translated_code
+ if code
+ code.translated_code
+ else
+ nil
+ end
+ end
+ end
+
+ # Symbol is both of nterm and term
+ # `number` is both for nterm and term
+ # `token_id` is tokentype for term, internal sequence number for nterm
+ #
+ # TODO: Add validation for ASCII code range for Token::Char
+ Symbol = Struct.new(:id, :alias_name, :number, :tag, :term, :token_id, :nullable, :precedence, :printer, keyword_init: true) do
+ attr_writer :eof_symbol, :error_symbol, :undef_symbol, :accept_symbol
+
+ def term?
+ term
+ end
+
+ def nterm?
+ !term
+ end
+
+ def eof_symbol?
+ !!@eof_symbol
+ end
+
+ def error_symbol?
+ !!@error_symbol
+ end
+
+ def undef_symbol?
+ !!@undef_symbol
+ end
+
+ def accept_symbol?
+ !!@accept_symbol
+ end
+
+ def display_name
+ if alias_name
+ alias_name
+ else
+ id.s_value
+ end
+ end
+
+ # name for yysymbol_kind_t
+ #
+ # See: b4_symbol_kind_base
+ def enum_name
+ case
+ when accept_symbol?
+ name = "YYACCEPT"
+ when eof_symbol?
+ name = "YYEOF"
+ when term? && id.type == Token::Char
+ if alias_name
+ name = number.to_s + alias_name
+ else
+ name = number.to_s + id.s_value
+ end
+ when term? && id.type == Token::Ident
+ name = id.s_value
+ when nterm? && (id.s_value.include?("$") || id.s_value.include?("@"))
+ name = number.to_s + id.s_value
+ when nterm?
+ name = id.s_value
+ else
+ raise "Unexpected #{self}"
+ end
+
+ "YYSYMBOL_" + name.gsub(/[^a-zA-Z_0-9]+/, "_")
+ end
+
+ # comment for yysymbol_kind_t
+ def comment
+ case
+ when accept_symbol?
+ # YYSYMBOL_YYACCEPT
+ id.s_value
+ when eof_symbol?
+ # YYEOF
+ alias_name
+ when (term? && 0 < token_id && token_id < 128)
+ # YYSYMBOL_3_backslash_, YYSYMBOL_14_
+ alias_name || id.s_value
+ when id.s_value.include?("$") || id.s_value.include?("@")
+ # YYSYMBOL_21_1
+ id.s_value
+ else
+ # YYSYMBOL_keyword_class, YYSYMBOL_strings_1
+ alias_name || id.s_value
+ end
+ end
+ end
+
+ Type = Struct.new(:id, :tag, keyword_init: true)
+
+ Code = Struct.new(:type, :token_code, keyword_init: true) do
+ extend Forwardable
+
+ def_delegators "token_code", :s_value, :line, :column, :references
+
+ # $$, $n, @$, @n is translated to C code
+ def translated_code
+ case type
+ when :user_code
+ translated_user_code
+ when :initial_action
+ translated_initial_action_code
+ end
+ end
+
+ # * ($1) error
+ # * ($$) *yyvaluep
+ # * (@1) error
+ # * (@$) *yylocationp
+ def translated_printer_code(tag)
+ t_code = s_value.dup
+
+ references.reverse.each do |ref|
+ first_column = ref.first_column
+ last_column = ref.last_column
+
+ case
+ when ref.number == "$" && ref.type == :dollar # $$
+ # Omit "<>"
+ member = tag.s_value[1..-2]
+ str = "((*yyvaluep).#{member})"
+ when ref.number == "$" && ref.type == :at # @$
+ str = "(*yylocationp)"
+ when ref.type == :dollar # $n
+ raise "$#{ref.number} can not be used in %printer."
+ when ref.type == :at # @n
+ raise "@#{ref.number} can not be used in %printer."
+ else
+ raise "Unexpected. #{code}, #{ref}"
+ end
+
+ t_code[first_column..last_column] = str
+ end
+
+ return t_code
+ end
+
+
+ private
+
+ # * ($1) yyvsp[i]
+ # * ($$) yyval
+ # * (@1) yylsp[i]
+ # * (@$) yyloc
+ def translated_user_code
+ t_code = s_value.dup
+
+ references.reverse.each do |ref|
+ first_column = ref.first_column
+ last_column = ref.last_column
+
+ case
+ when ref.number == "$" && ref.type == :dollar # $$
+ # Omit "<>"
+ member = ref.tag.s_value[1..-2]
+ str = "(yyval.#{member})"
+ when ref.number == "$" && ref.type == :at # @$
+ str = "(yyloc)"
+ when ref.type == :dollar # $n
+ i = -ref.position_in_rhs + ref.number
+ # Omit "<>"
+ member = ref.tag.s_value[1..-2]
+ str = "(yyvsp[#{i}].#{member})"
+ when ref.type == :at # @n
+ i = -ref.position_in_rhs + ref.number
+ str = "(yylsp[#{i}])"
+ else
+ raise "Unexpected. #{code}, #{ref}"
+ end
+
+ t_code[first_column..last_column] = str
+ end
+
+ return t_code
+ end
+
+ # * ($1) error
+ # * ($$) yylval
+ # * (@1) error
+ # * (@$) yylloc
+ def translated_initial_action_code
+ t_code = s_value.dup
+
+ references.reverse.each do |ref|
+ first_column = ref.first_column
+ last_column = ref.last_column
+
+ case
+ when ref.number == "$" && ref.type == :dollar # $$
+ str = "yylval"
+ when ref.number == "$" && ref.type == :at # @$
+ str = "yylloc"
+ when ref.type == :dollar # $n
+ raise "$#{ref.number} can not be used in initial_action."
+ when ref.type == :at # @n
+ raise "@#{ref.number} can not be used in initial_action."
+ else
+ raise "Unexpected. #{code}, #{ref}"
+ end
+
+ t_code[first_column..last_column] = str
+ end
+
+ return t_code
+ end
+ end
+
+ # type: :dollar or :at
+ # ex_tag: "$<tag>1" (Optional)
+ Reference = Struct.new(:type, :number, :ex_tag, :first_column, :last_column, :referring_symbol, :position_in_rhs, keyword_init: true) do
+ def tag
+ if ex_tag
+ ex_tag
+ else
+ referring_symbol.tag
+ end
+ end
+ end
+
+ Precedence = Struct.new(:type, :precedence, keyword_init: true) do
+ include Comparable
+
+ def <=>(other)
+ self.precedence <=> other.precedence
+ end
+ end
+
+ Printer = Struct.new(:ident_or_tags, :code, :lineno, keyword_init: true) do
+ def translated_code(member)
+ code.translated_printer_code(member)
+ end
+ end
+
+ Union = Struct.new(:code, :lineno, keyword_init: true) do
+ def braces_less_code
+ # Remove braces
+ code.s_value[1..-2]
+ end
+ end
+
+ Token = Lrama::Lexer::Token
+
+ # Grammar is the result of parsing an input grammar file
+ class Grammar
+ # Grammar file information not used by States but by Output
+ Aux = Struct.new(:prologue_first_lineno, :prologue, :epilogue_first_lineno, :epilogue, keyword_init: true)
+
+ attr_reader :eof_symbol, :error_symbol, :undef_symbol, :accept_symbol, :aux
+ attr_accessor :union, :expect,
+ :printers,
+ :lex_param, :parse_param, :initial_action,
+ :symbols, :types,
+ :rules, :_rules,
+ :sym_to_rules
+
+ def initialize
+ @printers = []
+ @symbols = []
+ @types = []
+ @_rules = []
+ @rules = []
+ @sym_to_rules = {}
+ @empty_symbol = nil
+ @eof_symbol = nil
+ @error_symbol = nil
+ @undef_symbol = nil
+ @accept_symbol = nil
+ @aux = Aux.new
+
+ append_special_symbols
+ end
+
+ def add_printer(ident_or_tags:, code:, lineno:)
+ @printers << Printer.new(ident_or_tags: ident_or_tags, code: code, lineno: lineno)
+ end
+
+ def add_term(id:, alias_name: nil, tag: nil, token_id: nil, replace: false)
+ if token_id && (sym = @symbols.find {|s| s.token_id == token_id })
+ if replace
+ sym.id = id
+ sym.alias_name = alias_name
+ sym.tag = tag
+ end
+
+ return sym
+ end
+
+ if sym = @symbols.find {|s| s.id == id }
+ return sym
+ end
+
+ sym = Symbol.new(
+ id: id, alias_name: alias_name, number: nil, tag: tag,
+ term: true, token_id: token_id, nullable: false
+ )
+ @symbols << sym
+ @terms = nil
+
+ return sym
+ end
+
+ def add_nterm(id:, alias_name: nil, tag: nil)
+ return if @symbols.find {|s| s.id == id }
+
+ sym = Symbol.new(
+ id: id, alias_name: alias_name, number: nil, tag: tag,
+ term: false, token_id: nil, nullable: nil,
+ )
+ @symbols << sym
+ @nterms = nil
+
+ return sym
+ end
+
+ def add_type(id:, tag:)
+ @types << Type.new(id: id, tag: tag)
+ end
+
+ def add_nonassoc(sym, precedence)
+ set_precedence(sym, Precedence.new(type: :nonassoc, precedence: precedence))
+ end
+
+ def add_left(sym, precedence)
+ set_precedence(sym, Precedence.new(type: :left, precedence: precedence))
+ end
+
+ def add_right(sym, precedence)
+ set_precedence(sym, Precedence.new(type: :right, precedence: precedence))
+ end
+
+ def set_precedence(sym, precedence)
+ raise "" if sym.nterm?
+ sym.precedence = precedence
+ end
+
+ def set_union(code, lineno)
+ @union = Union.new(code: code, lineno: lineno)
+ end
+
+ def add_rule(lhs:, rhs:, lineno:)
+ @_rules << [lhs, rhs, lineno]
+ end
+
+ def build_references(token_code)
+ token_code.references.map! do |type, number, tag, first_column, last_column|
+ Reference.new(type: type, number: number, ex_tag: tag, first_column: first_column, last_column: last_column)
+ end
+
+ token_code
+ end
+
+ def build_code(type, token_code)
+ build_references(token_code)
+ Code.new(type: type, token_code: token_code)
+ end
+
+ def prologue_first_lineno=(prologue_first_lineno)
+ @aux.prologue_first_lineno = prologue_first_lineno
+ end
+
+ def prologue=(prologue)
+ @aux.prologue = prologue
+ end
+
+ def epilogue_first_lineno=(epilogue_first_lineno)
+ @aux.epilogue_first_lineno = epilogue_first_lineno
+ end
+
+ def epilogue=(epilogue)
+ @aux.epilogue = epilogue
+ end
+
+ def prepare
+ normalize_rules
+ collect_symbols
+ replace_token_with_symbol
+ fill_symbol_number
+ fill_default_precedence
+ fill_sym_to_rules
+ fill_nterm_type
+ fill_symbol_printer
+ @symbols.sort_by!(&:number)
+ end
+
+ # TODO: More validation methods
+ def validate!
+ validate_symbol_number_uniqueness!
+ end
+
+ def compute_nullable
+ @rules.each do |rule|
+ case
+ when rule.rhs.empty?
+ rule.nullable = true
+ when rule.rhs.any?(&:term)
+ rule.nullable = false
+ else
+ # noop
+ end
+ end
+
+ while true do
+ rs = @rules.select {|e| e.nullable.nil? }
+ nts = nterms.select {|e| e.nullable.nil? }
+ rule_count_1 = rs.count
+ nterm_count_1 = nts.count
+
+ rs.each do |rule|
+ if rule.rhs.all?(&:nullable)
+ rule.nullable = true
+ end
+ end
+
+ nts.each do |nterm|
+ find_rules_by_symbol!(nterm).each do |rule|
+ if rule.nullable
+ nterm.nullable = true
+ end
+ end
+ end
+
+ rule_count_2 = @rules.count {|e| e.nullable.nil? }
+ nterm_count_2 = nterms.count {|e| e.nullable.nil? }
+
+ if (rule_count_1 == rule_count_2) && (nterm_count_1 == nterm_count_2)
+ break
+ end
+ end
+
+ rules.select {|r| r.nullable.nil? }.each do |rule|
+ rule.nullable = false
+ end
+
+ nterms.select {|r| r.nullable.nil? }.each do |nterm|
+ nterm.nullable = false
+ end
+ end
+
+ def find_symbol_by_s_value(s_value)
+ @symbols.find do |sym|
+ sym.id.s_value == s_value
+ end
+ end
+
+ def find_symbol_by_s_value!(s_value)
+ find_symbol_by_s_value(s_value) || (raise "Symbol not found: #{s_value}")
+ end
+
+ def find_symbol_by_id(id)
+ @symbols.find do |sym|
+ # TODO: validate uniqueness of Token#s_value and Symbol#alias_name
+ sym.id == id || sym.alias_name == id.s_value
+ end
+ end
+
+ def find_symbol_by_id!(id)
+ find_symbol_by_id(id) || (raise "Symbol not found: #{id}")
+ end
+
+ def find_symbol_by_number!(number)
+ sym = @symbols[number]
+
+ raise "Symbol not found: #{number}" unless sym
+ raise "[BUG] Symbol number mismatch. #{number}, #{sym}" if sym.number != number
+
+ sym
+ end
+
+ def find_rules_by_symbol!(sym)
+ find_rules_by_symbol(sym) || (raise "Rules for #{sym} not found")
+ end
+
+ def find_rules_by_symbol(sym)
+ @sym_to_rules[sym.number]
+ end
+
+ def terms_count
+ terms.count
+ end
+
+ def terms
+ @terms ||= @symbols.select(&:term?)
+ end
+
+ def nterms_count
+ nterms.count
+ end
+
+ def nterms
+ @nterms ||= @symbols.select(&:nterm?)
+ end
+
+ private
+
+ def find_nterm_by_id!(id)
+ nterms.find do |nterm|
+ nterm.id == id
+ end || (raise "Nterm not found: #{id}")
+ end
+
+
+ def append_special_symbols
+ # YYEMPTY (token_id: -2, number: -2) is added when a template is evaluated
+ # term = add_term(id: Token.new(Token::Ident, "YYEMPTY"), token_id: -2)
+ # term.number = -2
+ # @empty_symbol = term
+
+ # YYEOF
+ term = add_term(id: Token.new(type: Token::Ident, s_value: "YYEOF"), alias_name: "\"end of file\"", token_id: 0)
+ term.number = 0
+ term.eof_symbol = true
+ @eof_symbol = term
+
+ # YYerror
+ term = add_term(id: Token.new(type: Token::Ident, s_value: "YYerror"), alias_name: "error")
+ term.number = 1
+ term.error_symbol = true
+ @error_symbol = term
+
+ # YYUNDEF
+ term = add_term(id: Token.new(type: Token::Ident, s_value: "YYUNDEF"), alias_name: "\"invalid token\"")
+ term.number = 2
+ term.undef_symbol = true
+ @undef_symbol = term
+
+ # $accept
+ term = add_nterm(id: Token.new(type: Token::Ident, s_value: "$accept"))
+ term.accept_symbol = true
+ @accept_symbol = term
+ end
+
+ # 1. Add $accept rule to the top of rules
+ # 2. Extract precedence and last action
+ # 3. Extract action in the middle of RHS into new Empty rule
+ # 4. Append id and extract action then create Rule
+ #
+ # Bison 3.8.2 uses different orders for symbol number and rule number
+ # when a rule has actions in the middle of a rule.
+ #
+ # For example,
+ #
+ # `program: $@1 top_compstmt`
+ #
+ # Rules are ordered like below,
+ #
+ # 1 $@1: ε
+ # 2 program: $@1 top_compstmt
+ #
+ # Symbols are ordered like below,
+ #
+ # 164 program
+ # 165 $@1
+ #
+ def normalize_rules
+ # 1. Add $accept rule to the top of rules
+ accept = find_symbol_by_s_value!("$accept")
+ eof = find_symbol_by_number!(0)
+ lineno = @_rules.first ? @_rules.first[2] : 0
+ @rules << Rule.new(id: @rules.count, lhs: accept, rhs: [@_rules.first[0], eof], code: nil, lineno: lineno)
+
+ extracted_action_number = 1 # @n as nterm
+
+ @_rules.each do |lhs, rhs, lineno|
+ a = []
+ rhs1 = []
+ code = nil
+ precedence_sym = nil
+
+ # 2. Extract precedence and last action
+ rhs.reverse.each do |r|
+ case
+ when r.is_a?(Symbol) # precedence_sym
+ precedence_sym = r
+ when (r.type == Token::User_code) && precedence_sym.nil? && code.nil? && rhs1.empty?
+ code = r
+ else
+ rhs1 << r
+ end
+ end
+ rhs1.reverse!
+
+ # Bison n'th component is 1-origin
+ (rhs1 + [code]).compact.each.with_index(1) do |token, i|
+ if token.type == Token::User_code
+ token.references.each do |ref|
+ # Need to keep position_in_rhs for actions in the middle of RHS
+ ref.position_in_rhs = i - 1
+ next if ref.type == :at
+ # $$, $n, @$, @n can be used in any actions
+ number = ref.number
+
+ if number == "$"
+ # TODO: Should be postponed after middle actions are extracted?
+ ref.referring_symbol = lhs
+ else
+ raise "Can not refer following component. #{number} >= #{i}. #{token}" if number >= i
+ rhs1[number - 1].referred = true
+ ref.referring_symbol = rhs1[number - 1]
+ end
+ end
+ end
+ end
+
+ rhs2 = rhs1.map do |token|
+ if token.type == Token::User_code
+ prefix = token.referred ? "@" : "$@"
+ new_token = Token.new(type: Token::Ident, s_value: prefix + extracted_action_number.to_s)
+ extracted_action_number += 1
+ a << [new_token, token]
+ new_token
+ else
+ token
+ end
+ end
+
+ # Extract actions in the middle of RHS
+ # into new rules.
+ a.each do |new_token, code|
+ @rules << Rule.new(id: @rules.count, lhs: new_token, rhs: [], code: Code.new(type: :user_code, token_code: code), lineno: code.line)
+ end
+
+ c = code ? Code.new(type: :user_code, token_code: code) : nil
+ @rules << Rule.new(id: @rules.count, lhs: lhs, rhs: rhs2, code: c, precedence_sym: precedence_sym, lineno: lineno)
+
+ add_nterm(id: lhs)
+ a.each do |new_token, _|
+ add_nterm(id: new_token)
+ end
+ end
+ end
+
+ # Collect symbols from rules
+ def collect_symbols
+ @rules.flat_map(&:rhs).each do |s|
+ case s
+ when Token
+ if s.type == Token::Char
+ add_term(id: s)
+ end
+ when Symbol
+ # skip
+ else
+ raise "Unknown class: #{s}"
+ end
+ end
+ end
+
+ # Fill #number and #token_id
+ def fill_symbol_number
+ # TODO: why start from 256
+ token_id = 256
+
+ # YYEMPTY = -2
+ # YYEOF = 0
+ # YYerror = 1
+ # YYUNDEF = 2
+ number = 3
+
+ nterm_token_id = 0
+ used_numbers = {}
+
+ @symbols.map(&:number).each do |n|
+ used_numbers[n] = true
+ end
+
+ (@symbols.select(&:term?) + @symbols.select(&:nterm?)).each do |sym|
+ while used_numbers[number] do
+ number += 1
+ end
+
+ if sym.number.nil?
+ sym.number = number
+ number += 1
+ end
+
+ # If id is Token::Char, it uses ASCII code
+ if sym.term? && sym.token_id.nil?
+ if sym.id.type == Token::Char
+ # Igonre ' on the both sides
+ case sym.id.s_value[1..-2]
+ when "\\b"
+ sym.token_id = 8
+ when "\\f"
+ sym.token_id = 12
+ when "\\n"
+ sym.token_id = 10
+ when "\\r"
+ sym.token_id = 13
+ when "\\t"
+ sym.token_id = 9
+ when "\\v"
+ sym.token_id = 11
+ when "\""
+ sym.token_id = 34
+ when "\'"
+ sym.token_id = 39
+ when "\\\\"
+ sym.token_id = 92
+ when /\A\\(\d+)\z/
+ sym.token_id = Integer($1, 8)
+ when /\A(.)\z/
+ sym.token_id = $1.bytes.first
+ else
+ raise "Unknown Char s_value #{sym}"
+ end
+ else
+ sym.token_id = token_id
+ token_id += 1
+ end
+ end
+
+ if sym.nterm? && sym.token_id.nil?
+ sym.token_id = nterm_token_id
+ nterm_token_id += 1
+ end
+ end
+ end
+
+ def replace_token_with_symbol
+ @rules.each do |rule|
+ rule.lhs = token_to_symbol(rule.lhs)
+
+ rule.rhs.map! do |t|
+ token_to_symbol(t)
+ end
+
+ if rule.code
+ rule.code.references.each do |ref|
+ next if ref.type == :at
+
+ if ref.referring_symbol.type != Token::User_code
+ ref.referring_symbol = token_to_symbol(ref.referring_symbol)
+ end
+ end
+ end
+ end
+ end
+
+ def token_to_symbol(token)
+ case token
+ when Token
+ find_symbol_by_id!(token)
+ when Symbol
+ token
+ else
+ raise "Unknown class: #{token}"
+ end
+ end
+
+ # Rule inherits precedence from the last term in RHS.
+ #
+ # https://www.gnu.org/software/bison/manual/html_node/How-Precedence.html
+ def fill_default_precedence
+ @rules.each do |rule|
+ # Explicitly specified precedence has the highest priority
+ next if rule.precedence_sym
+
+ precedence_sym = nil
+ rule.rhs.each do |sym|
+ precedence_sym = sym if sym.term?
+ end
+
+ rule.precedence_sym = precedence_sym
+ end
+ end
+
+ def fill_sym_to_rules
+ @rules.each do |rule|
+ key = rule.lhs.number
+ @sym_to_rules[key] ||= []
+ @sym_to_rules[key] << rule
+ end
+ end
+
+ # Fill nterm's tag defined by %type decl
+ def fill_nterm_type
+ @types.each do |type|
+ nterm = find_nterm_by_id!(type.id)
+ nterm.tag = type.tag
+ end
+ end
+
+ def fill_symbol_printer
+ @symbols.each do |sym|
+ @printers.each do |printer|
+ printer.ident_or_tags.each do |ident_or_tag|
+ case ident_or_tag.type
+ when Token::Ident
+ sym.printer = printer if sym.id == ident_or_tag
+ when Token::Tag
+ sym.printer = printer if sym.tag == ident_or_tag
+ else
+ raise "Unknown token type. #{printer}"
+ end
+ end
+ end
+ end
+ end
+
+ def validate_symbol_number_uniqueness!
+ invalid = @symbols.group_by(&:number).select do |number, syms|
+ syms.count > 1
+ end
+
+ return if invalid.empty?
+
+ raise "Symbol number is dupulicated. #{invalid}"
+ end
+ end
+end
diff --git a/tool/lrama/lib/lrama/lexer.rb b/tool/lrama/lib/lrama/lexer.rb
new file mode 100644
index 0000000000..5c9583327b
--- /dev/null
+++ b/tool/lrama/lib/lrama/lexer.rb
@@ -0,0 +1,349 @@
+require "strscan"
+require "lrama/report"
+
+module Lrama
+ # Lexer for parse.y
+ class Lexer
+ include Lrama::Report::Duration
+
+ # s_value is semantic value
+ Token = Struct.new(:type, :s_value, keyword_init: true) do
+ Type = Struct.new(:id, :name, keyword_init: true)
+
+ attr_accessor :line, :column, :referred
+ # For User_code
+ attr_accessor :references
+
+ def to_s
+ "#{super} line: #{line}, column: #{column}"
+ end
+
+ @i = 0
+ @types = []
+
+ def self.define_type(name)
+ type = Type.new(id: @i, name: name.to_s)
+ const_set(name, type)
+ @types << type
+ @i += 1
+ end
+
+ # Token types
+ define_type(:P_expect) # %expect
+ define_type(:P_define) # %define
+ define_type(:P_printer) # %printer
+ define_type(:P_lex_param) # %lex-param
+ define_type(:P_parse_param) # %parse-param
+ define_type(:P_initial_action) # %initial-action
+ define_type(:P_union) # %union
+ define_type(:P_token) # %token
+ define_type(:P_type) # %type
+ define_type(:P_nonassoc) # %nonassoc
+ define_type(:P_left) # %left
+ define_type(:P_right) # %right
+ define_type(:P_prec) # %prec
+ define_type(:User_code) # { ... }
+ define_type(:Tag) # <int>
+ define_type(:Number) # 0
+ define_type(:Ident_Colon) # k_if:, k_if : (spaces can be there)
+ define_type(:Ident) # api.pure, tNUMBER
+ define_type(:Semicolon) # ;
+ define_type(:Bar) # |
+ define_type(:String) # "str"
+ define_type(:Char) # '+'
+ end
+
+ # States
+ #
+ # See: https://www.gnu.org/software/bison/manual/html_node/Grammar-Outline.html
+ Initial = 0
+ Prologue = 1
+ BisonDeclarations = 2
+ GrammarRules = 3
+ Epilogue = 4
+
+ # Token types
+
+ attr_reader :prologue, :bison_declarations, :grammar_rules, :epilogue,
+ :bison_declarations_tokens, :grammar_rules_tokens
+
+ def initialize(text)
+ @text = text
+ @state = Initial
+ # Array of texts
+ @prologue = []
+ @bison_declarations = []
+ @grammar_rules = []
+ @epilogue = []
+
+ #
+ @bison_declarations_tokens = []
+ @grammar_rules_tokens = []
+
+ @debug = false
+
+ report_duration(:lex) do
+ lex_text
+ lex_bison_declarations_tokens
+ lex_grammar_rules_tokens
+ end
+ end
+
+ private
+
+ def create_token(type, s_value, line, column)
+ t = Token.new(type: type, s_value: s_value)
+ t.line = line
+ t.column = column
+
+ return t
+ end
+
+ # TODO: Remove this
+ def lex_text
+ @text.each_line.with_index(1) do |string, lineno|
+ case @state
+ when Initial
+ # Skip until "%{"
+ if string == "%{\n"
+ @state = Prologue
+ @prologue << ["", lineno]
+ next
+ end
+ when Prologue
+ # Between "%{" and "%}"
+ if string == "%}\n"
+ @state = BisonDeclarations
+ @prologue << ["", lineno]
+ next
+ end
+
+ @prologue << [string, lineno]
+ when BisonDeclarations
+ if string == "%%\n"
+ @state = GrammarRules
+ next
+ end
+
+ @bison_declarations << [string, lineno]
+ when GrammarRules
+ # Between "%%" and "%%"
+ if string == "%%\n"
+ @state = Epilogue
+ next
+ end
+
+ @grammar_rules << [string, lineno]
+ when Epilogue
+ @epilogue << [string, lineno]
+ else
+ raise "Unknown state: #{@state}"
+ end
+ end
+ end
+
+ # See:
+ # * https://www.gnu.org/software/bison/manual/html_node/Decl-Summary.html
+ # * https://www.gnu.org/software/bison/manual/html_node/Symbol-Decls.html
+ # * https://www.gnu.org/software/bison/manual/html_node/Empty-Rules.html
+ def lex_common(lines, tokens)
+ line = lines.first[1]
+ column = 0
+ ss = StringScanner.new(lines.map(&:first).join)
+
+ while !ss.eos? do
+ case
+ when ss.scan(/\n/)
+ line += 1
+ column = ss.pos
+ when ss.scan(/\s+/)
+ # skip
+ when ss.scan(/;/)
+ tokens << create_token(Token::Semicolon, ss[0], line, ss.pos - column)
+ when ss.scan(/\|/)
+ tokens << create_token(Token::Bar, ss[0], line, ss.pos - column)
+ when ss.scan(/(\d+)/)
+ tokens << create_token(Token::Number, Integer(ss[0]), line, ss.pos - column)
+ when ss.scan(/(<[a-zA-Z0-9_]+>)/)
+ tokens << create_token(Token::Tag, ss[0], line, ss.pos - column)
+ when ss.scan(/([a-zA-Z_.][-a-zA-Z0-9_.]*)\s*:/)
+ tokens << create_token(Token::Ident_Colon, ss[1], line, ss.pos - column)
+ when ss.scan(/([a-zA-Z_.][-a-zA-Z0-9_.]*)/)
+ tokens << create_token(Token::Ident, ss[0], line, ss.pos - column)
+ when ss.scan(/%expect/)
+ tokens << create_token(Token::P_expect, ss[0], line, ss.pos - column)
+ when ss.scan(/%define/)
+ tokens << create_token(Token::P_define, ss[0], line, ss.pos - column)
+ when ss.scan(/%printer/)
+ tokens << create_token(Token::P_printer, ss[0], line, ss.pos - column)
+ when ss.scan(/%lex-param/)
+ tokens << create_token(Token::P_lex_param, ss[0], line, ss.pos - column)
+ when ss.scan(/%parse-param/)
+ tokens << create_token(Token::P_parse_param, ss[0], line, ss.pos - column)
+ when ss.scan(/%initial-action/)
+ tokens << create_token(Token::P_initial_action, ss[0], line, ss.pos - column)
+ when ss.scan(/%union/)
+ tokens << create_token(Token::P_union, ss[0], line, ss.pos - column)
+ when ss.scan(/%token/)
+ tokens << create_token(Token::P_token, ss[0], line, ss.pos - column)
+ when ss.scan(/%type/)
+ tokens << create_token(Token::P_type, ss[0], line, ss.pos - column)
+ when ss.scan(/%nonassoc/)
+ tokens << create_token(Token::P_nonassoc, ss[0], line, ss.pos - column)
+ when ss.scan(/%left/)
+ tokens << create_token(Token::P_left, ss[0], line, ss.pos - column)
+ when ss.scan(/%right/)
+ tokens << create_token(Token::P_right, ss[0], line, ss.pos - column)
+ when ss.scan(/%prec/)
+ tokens << create_token(Token::P_prec, ss[0], line, ss.pos - column)
+ when ss.scan(/{/)
+ token, line = lex_user_code(ss, line, ss.pos - column, lines)
+ tokens << token
+ when ss.scan(/"/)
+ string, line = lex_string(ss, "\"", line, lines)
+ token = create_token(Token::String, string, line, ss.pos - column)
+ tokens << token
+ when ss.scan(/\/\*/)
+ # TODO: Need to keep comment?
+ line = lex_comment(ss, line, lines, "")
+ when ss.scan(/'(.)'/)
+ tokens << create_token(Token::Char, ss[0], line, ss.pos - column)
+ when ss.scan(/'\\(.)'/) # '\\', '\t'
+ tokens << create_token(Token::Char, ss[0], line, ss.pos - column)
+ when ss.scan(/'\\(\d+)'/) # '\13'
+ tokens << create_token(Token::Char, ss[0], line, ss.pos - column)
+ when ss.scan(/%empty/)
+ # skip
+ else
+ l = line - lines.first[1]
+ split = ss.string.split("\n")
+ col = ss.pos - split[0...l].join("\n").length
+ raise "Parse error (unknow token): #{split[l]} \"#{ss.string[ss.pos]}\" (#{line}: #{col})"
+ end
+ end
+ end
+
+ def lex_bison_declarations_tokens
+ lex_common(@bison_declarations, @bison_declarations_tokens)
+ end
+
+ def lex_user_code(ss, line, column, lines)
+ first_line = line
+ first_column = column
+ debug("Enter lex_user_code: #{line}")
+ brace_count = 1
+ str = "{"
+ # Array of [type, $n, tag, first column, last column]
+ # TODO: Is it better to keep string, like "$$", and use gsub?
+ references = []
+
+ while !ss.eos? do
+ case
+ when ss.scan(/\n/)
+ line += 1
+ when ss.scan(/"/)
+ string, line = lex_string(ss, "\"", line, lines)
+ str << string
+ next
+ when ss.scan(/'/)
+ string, line = lex_string(ss, "'", line, lines)
+ str << string
+ next
+ when ss.scan(/\$(<[a-zA-Z0-9_]+>)?\$/) # $$, $<long>$
+ tag = ss[1] ? create_token(Token::Tag, ss[1], line, str.length) : nil
+ references << [:dollar, "$", tag, str.length, str.length + ss[0].length - 1]
+ when ss.scan(/\$(<[a-zA-Z0-9_]+>)?(\d+)/) # $1, $2, $<long>1
+ tag = ss[1] ? create_token(Token::Tag, ss[1], line, str.length) : nil
+ references << [:dollar, Integer(ss[2]), tag, str.length, str.length + ss[0].length - 1]
+ when ss.scan(/@\$/) # @$
+ references << [:at, "$", nil, str.length, str.length + ss[0].length - 1]
+ when ss.scan(/@(\d)+/) # @1
+ references << [:at, Integer(ss[1]), nil, str.length, str.length + ss[0].length - 1]
+ when ss.scan(/{/)
+ brace_count += 1
+ when ss.scan(/}/)
+ brace_count -= 1
+
+ debug("Return lex_user_code: #{line}")
+ if brace_count == 0
+ str << ss[0]
+ user_code = Token.new(type: Token::User_code, s_value: str.freeze)
+ user_code.line = first_line
+ user_code.column = first_column
+ user_code.references = references
+ return [user_code, line]
+ end
+ when ss.scan(/\/\*/)
+ str << ss[0]
+ line = lex_comment(ss, line, lines, str)
+ else
+ # noop, just consume char
+ str << ss.getch
+ next
+ end
+
+ str << ss[0]
+ end
+
+ # Reach to end of input but brace does not match
+ l = line - lines.first[1]
+ raise "Parse error (brace mismatch): #{ss.string.split("\n")[l]} \"#{ss.string[ss.pos]}\" (#{line}: #{ss.pos})"
+ end
+
+ def lex_string(ss, terminator, line, lines)
+ debug("Enter lex_string: #{line}")
+
+ str = terminator.dup
+
+ while (c = ss.getch) do
+ str << c
+
+ case c
+ when "\n"
+ line += 1
+ when terminator
+ debug("Return lex_string: #{line}")
+ return [str, line]
+ else
+ # noop
+ end
+ end
+
+ # Reach to end of input but quote does not match
+ l = line - lines.first[1]
+ raise "Parse error (quote mismatch): #{ss.string.split("\n")[l]} \"#{ss.string[ss.pos]}\" (#{line}: #{ss.pos})"
+ end
+
+ # TODO: Need to handle // style comment
+ #
+ # /* */ style comment
+ def lex_comment(ss, line, lines, str)
+ while !ss.eos? do
+ case
+ when ss.scan(/\n/)
+ line += 1
+ when ss.scan(/\*\//)
+ return line
+ else
+ str << ss.getch
+ next
+ end
+
+ str << ss[0]
+ end
+
+ # Reach to end of input but quote does not match
+ l = line - lines.first[1]
+ raise "Parse error (comment mismatch): #{ss.string.split("\n")[l]} \"#{ss.string[ss.pos]}\" (#{line}: #{ss.pos})"
+ end
+
+ def lex_grammar_rules_tokens
+ lex_common(@grammar_rules, @grammar_rules_tokens)
+ end
+
+ def debug(msg)
+ return unless @debug
+ puts "#{msg}\n"
+ end
+ end
+end
diff --git a/tool/lrama/lib/lrama/output.rb b/tool/lrama/lib/lrama/output.rb
new file mode 100644
index 0000000000..eaefbd04dc
--- /dev/null
+++ b/tool/lrama/lib/lrama/output.rb
@@ -0,0 +1,370 @@
+require "erb"
+require "forwardable"
+require "lrama/report"
+
+module Lrama
+ class Output
+ extend Forwardable
+ include Report::Duration
+
+ attr_reader :grammar_file_path, :context, :grammar
+
+ def_delegators "@context", :yyfinal, :yylast, :yyntokens, :yynnts, :yynrules, :yynstates,
+ :yymaxutok, :yypact_ninf, :yytable_ninf
+
+ def_delegators "@grammar", :eof_symbol, :error_symbol, :undef_symbol, :accept_symbol
+
+ def initialize(out:, output_file_path:, template_name:, grammar_file_path:, header_out: nil, header_file_path: nil, context:, grammar:)
+ @out = out
+ @output_file_path = output_file_path
+ @template_name = template_name
+ @grammar_file_path = grammar_file_path
+ @header_out = header_out
+ @header_file_path = header_file_path
+ @context = context
+ @grammar = grammar
+ end
+
+ if ERB.instance_method(:initialize).parameters.last.first == :key
+ def self.erb(input)
+ ERB.new(input, trim_mode: '-')
+ end
+ else
+ def self.erb(input)
+ ERB.new(input, nil, '-')
+ end
+ end
+
+ def eval_template(file, path)
+ erb = self.class.erb(File.read(file))
+ erb.filename = file
+ tmp = erb.result_with_hash(context: @context, output: self)
+ replace_special_variables(tmp, path)
+ end
+
+ def render
+ report_duration(:render) do
+ tmp = eval_template(template_file, @output_file_path)
+ @out << tmp
+
+ if @header_file_path
+ tmp = eval_template(header_template_file, @header_file_path)
+
+ if @header_out
+ @header_out << tmp
+ else
+ File.open(@header_file_path, "w+") do |f|
+ f << tmp
+ end
+ end
+ end
+ end
+ end
+
+ # A part of b4_token_enums
+ def token_enums
+ str = ""
+
+ @context.yytokentype.each do |s_value, token_id, display_name|
+ s = sprintf("%s = %d%s", s_value, token_id, token_id == yymaxutok ? "" : ",")
+
+ if display_name
+ str << sprintf(" %-30s /* %s */\n", s, display_name)
+ else
+ str << sprintf(" %s\n", s)
+ end
+ end
+
+ str
+ end
+
+ # b4_symbol_enum
+ def symbol_enum
+ str = ""
+
+ last_sym_number = @context.yysymbol_kind_t.last[1]
+ @context.yysymbol_kind_t.each do |s_value, sym_number, display_name|
+ s = sprintf("%s = %d%s", s_value, sym_number, (sym_number == last_sym_number) ? "" : ",")
+
+ if display_name
+ str << sprintf(" %-40s /* %s */\n", s, display_name)
+ else
+ str << sprintf(" %s\n", s)
+ end
+ end
+
+ str
+ end
+
+ def yytranslate
+ int_array_to_string(@context.yytranslate)
+ end
+
+ def yyrline
+ int_array_to_string(@context.yyrline)
+ end
+
+ def yytname
+ string_array_to_string(@context.yytname) + " YY_NULLPTR"
+ end
+
+ # b4_int_type_for
+ def int_type_for(ary)
+ min = ary.min
+ max = ary.max
+
+ case
+ when (-127 <= min && min <= 127) && (-127 <= max && max <= 127)
+ "yytype_int8"
+ when (0 <= min && min <= 255) && (0 <= max && max <= 255)
+ "yytype_uint8"
+ when (-32767 <= min && min <= 32767) && (-32767 <= max && max <= 32767)
+ "yytype_int16"
+ when (0 <= min && min <= 65535) && (0 <= max && max <= 65535)
+ "yytype_uint16"
+ else
+ "int"
+ end
+ end
+
+ def symbol_actions_for_printer
+ str = ""
+
+ @grammar.symbols.each do |sym|
+ next unless sym.printer
+
+ str << <<-STR
+ case #{sym.enum_name}: /* #{sym.comment} */
+#line #{sym.printer.lineno} "#{@grammar_file_path}"
+ #{sym.printer.translated_code(sym.tag)}
+#line [@oline@] [@ofile@]
+ break;
+
+ STR
+ end
+
+ str
+ end
+
+ # b4_user_initial_action
+ def user_initial_action(comment = "")
+ return "" unless @grammar.initial_action
+
+ <<-STR
+ #{comment}
+#line #{@grammar.initial_action.line} "#{@grammar_file_path}"
+ #{@grammar.initial_action.translated_code}
+ STR
+ end
+
+ # b4_user_actions
+ def user_actions
+ str = ""
+
+ @context.states.rules.each do |rule|
+ next unless rule.code
+
+ rule = rule
+ code = rule.code
+ spaces = " " * (code.column - 1)
+
+ str << <<-STR
+ case #{rule.id + 1}: /* #{rule.as_comment} */
+#line #{code.line} "#{@grammar_file_path}"
+#{spaces}#{rule.translated_code}
+#line [@oline@] [@ofile@]
+ break;
+
+ STR
+ end
+
+ str << <<-STR
+
+#line [@oline@] [@ofile@]
+ STR
+
+ str
+ end
+
+ def omit_braces_and_blanks(param)
+ param[1..-2].strip
+ end
+
+ # b4_parse_param
+ def parse_param
+ if @grammar.parse_param
+ omit_braces_and_blanks(@grammar.parse_param)
+ else
+ ""
+ end
+ end
+
+ def lex_param
+ if @grammar.lex_param
+ omit_braces_and_blanks(@grammar.lex_param)
+ else
+ ""
+ end
+ end
+
+ # b4_user_formals
+ def user_formals
+ if @grammar.parse_param
+ ", #{parse_param}"
+ else
+ ""
+ end
+ end
+
+ # b4_user_args
+ def user_args
+ if @grammar.parse_param
+ ", #{parse_param_name}"
+ else
+ ""
+ end
+ end
+
+ def extract_param_name(param)
+ /\A(.)+([a-zA-Z0-9_]+)\z/.match(param)[2]
+ end
+
+ def parse_param_name
+ if @grammar.parse_param
+ extract_param_name(parse_param)
+ else
+ ""
+ end
+ end
+
+ def lex_param_name
+ if @grammar.lex_param
+ extract_param_name(lex_param)
+ else
+ ""
+ end
+ end
+
+ # b4_parse_param_use
+ def parse_param_use(val, loc)
+ str = <<-STR
+ YY_USE (#{val});
+ YY_USE (#{loc});
+ STR
+
+ if @grammar.parse_param
+ str << " YY_USE (#{parse_param_name});"
+ end
+
+ str
+ end
+
+ # b4_yylex_formals
+ def yylex_formals
+ ary = ["&yylval", "&yylloc"]
+
+ if @grammar.lex_param
+ ary << lex_param_name
+ end
+
+ "(#{ary.join(', ')})"
+ end
+
+ # b4_table_value_equals
+ def table_value_equals(table, value, literal, symbol)
+ if literal < table.min || table.max < literal
+ "0"
+ else
+ "((#{value}) == #{symbol})"
+ end
+ end
+
+ # b4_yyerror_args
+ def yyerror_args
+ ary = ["&yylloc"]
+
+ if @grammar.parse_param
+ ary << parse_param_name
+ end
+
+ "#{ary.join(', ')}"
+ end
+
+ def template_basename
+ File.basename(template_file)
+ end
+
+ def aux
+ @grammar.aux
+ end
+
+ def int_array_to_string(ary)
+ last = ary.count - 1
+
+ s = ary.each_with_index.each_slice(10).map do |slice|
+ str = " "
+
+ slice.each do |e, i|
+ str << sprintf("%6d%s", e, (i == last) ? "" : ",")
+ end
+
+ str
+ end
+
+ s.join("\n")
+ end
+
+ def spec_mapped_header_file
+ @header_file_path
+ end
+
+ def b4_cpp_guard__b4_spec_mapped_header_file
+ if @header_file_path
+ "YY_YY_" + @header_file_path.gsub(/[^a-zA-Z_0-9]+/, "_").upcase + "_INCLUDED"
+ else
+ ""
+ end
+ end
+
+ private
+
+ def template_file
+ File.join(template_dir, @template_name)
+ end
+
+ def header_template_file
+ File.join(template_dir, "bison/yacc.h")
+ end
+
+ def template_dir
+ File.expand_path("../../../template", __FILE__)
+ end
+
+ def string_array_to_string(ary)
+ str = ""
+ tmp = " "
+
+ ary.each do |s|
+ s = s.gsub('\\', '\\\\\\\\')
+ s = s.gsub('"', '\\"')
+
+ if (tmp + s + " \"\",").length > 75
+ str << tmp << "\n"
+ tmp = " \"#{s}\","
+ else
+ tmp << " \"#{s}\","
+ end
+ end
+
+ str << tmp
+ end
+
+ def replace_special_variables(str, ofile)
+ str.each_line.with_index(1).map do |line, i|
+ line.gsub!("[@oline@]", (i + 1).to_s)
+ line.gsub!("[@ofile@]", "\"#{ofile}\"")
+ line
+ end.join
+ end
+ end
+end
diff --git a/tool/lrama/lib/lrama/parser.rb b/tool/lrama/lib/lrama/parser.rb
new file mode 100644
index 0000000000..e90a94c637
--- /dev/null
+++ b/tool/lrama/lib/lrama/parser.rb
@@ -0,0 +1,321 @@
+require "lrama/report"
+
+module Lrama
+ # Parser for parse.y, generates a grammar
+ class Parser
+ include Lrama::Report::Duration
+
+ T = Lrama::Lexer::Token
+
+ class TokenScanner
+ def initialize(tokens)
+ @tokens = tokens
+ @index = 0
+ end
+
+ def current_token
+ @tokens[@index]
+ end
+
+ def current_type
+ current_token && current_token.type
+ end
+
+ def next
+ token = current_token
+ @index += 1
+ return token
+ end
+
+ def consume(*token_types)
+ if token_types.include?(current_type)
+ token = current_token
+ self.next
+ return token
+ end
+
+ return nil
+ end
+
+ def consume!(*token_types)
+ consume(*token_types) || (raise "#{token_types} is expected but #{current_type}. #{current_token}")
+ end
+
+ def consume_multi(*token_types)
+ a = []
+
+ while token_types.include?(current_type)
+ a << current_token
+ self.next
+ end
+
+ raise "No token is consumed. #{token_types}" if a.empty?
+
+ return a
+ end
+
+ def eots?
+ current_token.nil?
+ end
+ end
+
+ def initialize(text)
+ @text = text
+ end
+
+ def parse
+ report_duration(:parse) do
+ lexer = Lexer.new(@text)
+ grammar = Grammar.new
+ process_prologue(grammar, lexer)
+ parse_bison_declarations(TokenScanner.new(lexer.bison_declarations_tokens), grammar)
+ parse_grammar_rules(TokenScanner.new(lexer.grammar_rules_tokens), grammar)
+ process_epilogue(grammar, lexer)
+ grammar.prepare
+ grammar.compute_nullable
+ grammar.validate!
+
+ grammar
+ end
+ end
+
+ private
+
+ def process_prologue(grammar, lexer)
+ grammar.prologue_first_lineno = lexer.prologue.first[1] if lexer.prologue.first
+ grammar.prologue = lexer.prologue.map(&:first).join
+ end
+
+ def process_epilogue(grammar, lexer)
+ grammar.epilogue_first_lineno = lexer.epilogue.first[1] if lexer.epilogue.first
+ grammar.epilogue = lexer.epilogue.map(&:first).join
+ end
+
+ def parse_bison_declarations(ts, grammar)
+ precedence_number = 0
+
+ while !ts.eots? do
+ case ts.current_type
+ when T::P_expect
+ ts.next
+ grammar.expect = ts.consume!(T::Number).s_value
+ when T::P_define
+ ts.next
+ # Ignore
+ ts.consume_multi(T::Ident)
+ when T::P_printer
+ lineno = ts.current_token.line
+ ts.next
+ code = ts.consume!(T::User_code)
+ code = grammar.build_code(:printer, code)
+ ident_or_tags = ts.consume_multi(T::Ident, T::Tag)
+ grammar.add_printer(ident_or_tags: ident_or_tags, code: code, lineno: lineno)
+ when T::P_lex_param
+ ts.next
+ code = ts.consume!(T::User_code)
+ code = grammar.build_code(:lex_param, code)
+ grammar.lex_param = code.token_code.s_value
+ when T::P_parse_param
+ ts.next
+ code = ts.consume!(T::User_code)
+ code = grammar.build_code(:parse_param, code)
+ grammar.parse_param = code.token_code.s_value
+ when T::P_initial_action
+ ts.next
+ code = ts.consume!(T::User_code)
+ code = grammar.build_code(:initial_action, code)
+ ts.consume(T::Semicolon)
+ grammar.initial_action = code
+ when T::P_union
+ lineno = ts.current_token.line
+ ts.next
+ code = ts.consume!(T::User_code)
+ code = grammar.build_code(:union, code)
+ ts.consume(T::Semicolon)
+ grammar.set_union(code, lineno)
+ when T::P_token
+ # %token tag? (ident number? string?)+
+ #
+ # * ident can be char, e.g. '\\', '\t', '\13'
+ # * number is a token_id for term
+ #
+ # These are valid token declaration (from CRuby parse.y)
+ #
+ # %token END_OF_INPUT 0 "end-of-input"
+ # %token <id> '\\' "backslash"
+ # %token tSP "escaped space"
+ # %token tUPLUS 132 "unary+"
+ # %token tCOLON3 ":: at EXPR_BEG"
+ # %token tSTRING_DBEG tSTRING_DVAR tLAMBEG tLABEL_END
+ #
+ #
+ # See: https://www.gnu.org/software/bison/manual/html_node/Symbol-Decls.html
+ ts.next
+ opt_tag = ts.consume(T::Tag)
+
+ while (id = ts.consume(T::Ident, T::Char)) do
+ opt_number = ts.consume(T::Number)
+ opt_string = ts.consume(T::String)
+ # Can replace 0 (EOF)
+ grammar.add_term(
+ id: id,
+ alias_name: opt_string && opt_string.s_value,
+ token_id: opt_number && opt_number.s_value,
+ tag: opt_tag,
+ replace: true,
+ )
+ end
+ when T::P_type
+ # %type tag? (ident|char|string)+
+ #
+ # See: https://www.gnu.org/software/bison/manual/html_node/Symbol-Decls.html
+ ts.next
+ opt_tag = ts.consume(T::Tag)
+
+ while (id = ts.consume(T::Ident, T::Char, T::String)) do
+ grammar.add_type(
+ id: id,
+ tag: opt_tag
+ )
+ end
+ when T::P_nonassoc
+ # %nonassoc (ident|char|string)+
+ ts.next
+ while (id = ts.consume(T::Ident, T::Char, T::String)) do
+ sym = grammar.add_term(id: id)
+ grammar.add_nonassoc(sym, precedence_number)
+ end
+ precedence_number += 1
+ when T::P_left
+ # %left (ident|char|string)+
+ ts.next
+ while (id = ts.consume(T::Ident, T::Char, T::String)) do
+ sym = grammar.add_term(id: id)
+ grammar.add_left(sym, precedence_number)
+ end
+ precedence_number += 1
+ when T::P_right
+ # %right (ident|char|string)+
+ ts.next
+ while (id = ts.consume(T::Ident, T::Char, T::String)) do
+ sym = grammar.add_term(id: id)
+ grammar.add_right(sym, precedence_number)
+ end
+ precedence_number += 1
+ when nil
+ # end of input
+ raise "Reach to end of input within declarations"
+ else
+ raise "Unexpected token: #{ts.current_token}"
+ end
+ end
+ end
+
+ def parse_grammar_rules(ts, grammar)
+ while !ts.eots? do
+ parse_grammar_rule(ts, grammar)
+ end
+ end
+
+ # TODO: Take care of %prec of rule.
+ # If %prec exists, user code before %prec
+ # is NOT an action. For example "{ code 3 }" is NOT an action.
+ #
+ # keyword_class { code 2 } tSTRING '!' keyword_end { code 3 } %prec "="
+ def parse_grammar_rule(ts, grammar)
+ # LHS
+ lhs = ts.consume!(T::Ident_Colon) # class:
+ lhs.type = T::Ident
+
+ rhs = parse_grammar_rule_rhs(ts, grammar)
+
+ grammar.add_rule(lhs: lhs, rhs: rhs, lineno: rhs.first ? rhs.first.line : lhs.line)
+
+ while true do
+ case ts.current_type
+ when T::Bar
+ # |
+ bar_lineno = ts.current_token.line
+ ts.next
+ rhs = parse_grammar_rule_rhs(ts, grammar)
+ grammar.add_rule(lhs: lhs, rhs: rhs, lineno: rhs.first ? rhs.first.line : bar_lineno)
+ when T::Semicolon
+ # ;
+ ts.next
+ break
+ when T::Ident_Colon
+ # Next lhs can be here because ";" is optional.
+ # Do not consume next token.
+ break
+ when nil
+ # end of input can be here when ";" is omitted
+ break
+ else
+ raise "Unexpected token: #{ts.current_token}"
+ end
+ end
+ end
+
+ def parse_grammar_rule_rhs(ts, grammar)
+ a = []
+ prec_seen = false
+ code_after_prec = false
+
+ while true do
+ # TODO: Srting can be here
+ case ts.current_type
+ when T::Ident
+ # keyword_class
+
+ raise "Ident after %prec" if prec_seen
+ a << ts.current_token
+ ts.next
+ when T::Char
+ # '!'
+
+ raise "Char after %prec" if prec_seen
+ a << ts.current_token
+ ts.next
+ when T::P_prec
+ # %prec tPLUS
+ #
+ # See: https://www.gnu.org/software/bison/manual/html_node/Contextual-Precedence.html
+
+ ts.next
+ prec_seen = true
+ precedence_id = ts.consume!(T::Ident, T::String, T::Char)
+ precedence_sym = grammar.find_symbol_by_id!(precedence_id)
+ a << precedence_sym
+ when T::User_code
+ # { code } in the middle of rhs
+
+ if prec_seen
+ raise "Multiple User_code after %prec" if code_after_prec
+ code_after_prec = true
+ end
+
+ code = ts.current_token
+ grammar.build_references(code)
+ a << code
+ ts.next
+ when T::Bar
+ # |
+ break
+ when T::Semicolon
+ # ;
+ break
+ when T::Ident_Colon
+ # Next lhs can be here because ";" is optional.
+ break
+ when nil
+ # end of input can be here when ";" is omitted
+ break
+ else
+ raise "Unexpected token: #{ts.current_token}"
+ end
+ end
+
+ return a
+ end
+ end
+end
diff --git a/tool/lrama/lib/lrama/report.rb b/tool/lrama/lib/lrama/report.rb
new file mode 100644
index 0000000000..7016a45171
--- /dev/null
+++ b/tool/lrama/lib/lrama/report.rb
@@ -0,0 +1,47 @@
+module Lrama
+ class Report
+ module Profile
+ # 1. Wrap target method with Profile.report_profile like below:
+ #
+ # Lrama::Report::Profile.report_profile { method }
+ #
+ # 2. Run lrama command, for example
+ #
+ # $ ./exe/lrama --trace=time spec/fixtures/integration/ruby_3_2_0/parse.tmp.y
+ #
+ # 3. Generate html file
+ #
+ # $ stackprof --d3-flamegraph tmp/stackprof-cpu-myapp.dump > tmp/flamegraph.html
+ #
+ def self.report_profile
+ require "stackprof"
+
+ StackProf.run(mode: :cpu, raw: true, out: 'tmp/stackprof-cpu-myapp.dump') do
+ yield
+ end
+ end
+ end
+
+ module Duration
+ def self.enable
+ @_report_duration_enabled = true
+ end
+
+ def self.enabled?
+ !!@_report_duration_enabled
+ end
+
+ def report_duration(method_name)
+ time1 = Time.now.to_f
+ result = yield
+ time2 = Time.now.to_f
+
+ if Duration.enabled?
+ puts sprintf("%s %10.5f s", method_name, time2 - time1)
+ end
+
+ return result
+ end
+ end
+ end
+end
diff --git a/tool/lrama/lib/lrama/states.rb b/tool/lrama/lib/lrama/states.rb
new file mode 100644
index 0000000000..f907db30cc
--- /dev/null
+++ b/tool/lrama/lib/lrama/states.rb
@@ -0,0 +1,832 @@
+require "forwardable"
+require "lrama/report"
+
+module Lrama
+ class State
+ class Reduce
+ # https://www.gnu.org/software/bison/manual/html_node/Default-Reductions.html
+ attr_reader :item, :look_ahead, :not_selected_symbols
+ attr_accessor :default_reduction
+
+ def initialize(item)
+ @item = item
+ @look_ahead = nil
+ @not_selected_symbols = []
+ end
+
+ def rule
+ @item.rule
+ end
+
+ def look_ahead=(look_ahead)
+ @look_ahead = look_ahead.freeze
+ end
+
+ def add_not_selected_symbol(sym)
+ @not_selected_symbols << sym
+ end
+
+ def selected_look_ahead
+ if @look_ahead
+ @look_ahead - @not_selected_symbols
+ else
+ []
+ end
+ end
+ end
+
+ class Shift
+ attr_reader :next_sym, :next_items
+ attr_accessor :not_selected
+
+ def initialize(next_sym, next_items)
+ @next_sym = next_sym
+ @next_items = next_items
+ end
+ end
+
+ # * symbol: A symbol under discussion
+ # * reduce: A reduce under discussion
+ # * which: For which a conflict is resolved. :shift, :reduce or :error (for nonassociative)
+ ResolvedConflict = Struct.new(:symbol, :reduce, :which, :same_prec, keyword_init: true) do
+ def report_message
+ s = symbol.display_name
+ r = reduce.rule.precedence_sym.display_name
+ case
+ when which == :shift && same_prec
+ msg = "resolved as #{which} (%right #{s})"
+ when which == :shift
+ msg = "resolved as #{which} (#{r} < #{s})"
+ when which == :reduce && same_prec
+ msg = "resolved as #{which} (%left #{s})"
+ when which == :reduce
+ msg = "resolved as #{which} (#{s} < #{r})"
+ when which == :error
+ msg = "resolved as an #{which} (%nonassoc #{s})"
+ else
+ raise "Unknown direction. #{self}"
+ end
+
+ "Conflict between rule #{reduce.rule.id} and token #{s} #{msg}."
+ end
+ end
+
+ Conflict = Struct.new(:symbols, :reduce, :type, keyword_init: true)
+
+ attr_reader :id, :accessing_symbol, :kernels, :conflicts, :resolved_conflicts,
+ :default_reduction_rule, :closure, :items
+ attr_accessor :shifts, :reduces
+
+ def initialize(id, accessing_symbol, kernels)
+ @id = id
+ @accessing_symbol = accessing_symbol
+ @kernels = kernels.freeze
+ @items = @kernels
+ # Manage relationships between items to state
+ # to resolve next state
+ @items_to_state = {}
+ @conflicts = []
+ @resolved_conflicts = []
+ @default_reduction_rule = nil
+ end
+
+ def closure=(closure)
+ @closure = closure
+ @items = @kernels + @closure
+ end
+
+ def non_default_reduces
+ reduces.select do |reduce|
+ reduce.rule != @default_reduction_rule
+ end
+ end
+
+ def compute_shifts_reduces
+ _shifts = {}
+ reduces = []
+ items.each do |item|
+ # TODO: Consider what should be pushed
+ if item.end_of_rule?
+ reduces << Reduce.new(item)
+ else
+ key = item.next_sym
+ _shifts[key] ||= []
+ _shifts[key] << item.new_by_next_position
+ end
+ end
+
+ # It seems Bison 3.8.2 iterates transitions order by symbol number
+ shifts = _shifts.sort_by do |next_sym, new_items|
+ next_sym.number
+ end.map do |next_sym, new_items|
+ Shift.new(next_sym, new_items.flatten)
+ end
+ self.shifts = shifts.freeze
+ self.reduces = reduces.freeze
+ end
+
+ def set_items_to_state(items, next_state)
+ @items_to_state[items] = next_state
+ end
+
+ #
+ def set_look_ahead(rule, look_ahead)
+ reduce = reduces.find do |r|
+ r.rule == rule
+ end
+
+ reduce.look_ahead = look_ahead
+ end
+
+ # Returns array of [nterm, next_state]
+ def nterm_transitions
+ return @nterm_transitions if @nterm_transitions
+
+ @nterm_transitions = []
+
+ shifts.each do |shift|
+ next if shift.next_sym.term?
+
+ @nterm_transitions << [shift, @items_to_state[shift.next_items]]
+ end
+
+ @nterm_transitions
+ end
+
+ # Returns array of [term, next_state]
+ def term_transitions
+ return @term_transitions if @term_transitions
+
+ @term_transitions = []
+
+ shifts.each do |shift|
+ next if shift.next_sym.nterm?
+
+ @term_transitions << [shift, @items_to_state[shift.next_items]]
+ end
+
+ @term_transitions
+ end
+
+ def selected_term_transitions
+ term_transitions.select do |shift, next_state|
+ !shift.not_selected
+ end
+ end
+
+ # Move to next state by sym
+ def transition(sym)
+ result = nil
+
+ if sym.term?
+ term_transitions.each do |shift, next_state|
+ term = shift.next_sym
+ result = next_state if term == sym
+ end
+ else
+ nterm_transitions.each do |shift, next_state|
+ nterm = shift.next_sym
+ result = next_state if nterm == sym
+ end
+ end
+
+ raise "Can not transit by #{sym} #{self}" if result.nil?
+
+ result
+ end
+
+ def find_reduce_by_item!(item)
+ reduces.find do |r|
+ r.item == item
+ end || (raise "reduce is not found. #{item}, #{state}")
+ end
+
+ def default_reduction_rule=(default_reduction_rule)
+ @default_reduction_rule = default_reduction_rule
+
+ reduces.each do |r|
+ if r.rule == default_reduction_rule
+ r.default_reduction = true
+ end
+ end
+ end
+
+ def sr_conflicts
+ @conflicts.select do |conflict|
+ conflict.type == :shift_reduce
+ end
+ end
+
+ def rr_conflicts
+ @conflicts.select do |conflict|
+ conflict.type == :reduce_reduce
+ end
+ end
+ end
+
+ # States is passed to a template file
+ #
+ # "Efficient Computation of LALR(1) Look-Ahead Sets"
+ # https://dl.acm.org/doi/pdf/10.1145/69622.357187
+ class States
+ extend Forwardable
+ include Lrama::Report::Duration
+
+ def_delegators "@grammar", :symbols, :terms, :nterms, :rules,
+ :accept_symbol, :eof_symbol, :find_symbol_by_s_value!
+
+ # TODO: Validate position is not over rule rhs
+ Item = Struct.new(:rule, :position, keyword_init: true) do
+ # Optimization for States#setup_state
+ def hash
+ [rule.id, position].hash
+ end
+
+ def rule_id
+ rule.id
+ end
+
+ def next_sym
+ rule.rhs[position]
+ end
+
+ def end_of_rule?
+ rule.rhs.count == position
+ end
+
+ def new_by_next_position
+ Item.new(rule: rule, position: position + 1)
+ end
+
+ def previous_sym
+ rule.rhs[position - 1]
+ end
+
+ def display_name
+ r = rule.rhs.map(&:display_name).insert(position, "•").join(" ")
+ "#{r} (rule #{rule.id})"
+ end
+
+ # Right after position
+ def display_rest
+ r = rule.rhs[position..-1].map(&:display_name).join(" ")
+ ". #{r} (rule #{rule.id})"
+ end
+ end
+
+ attr_reader :states, :reads_relation, :includes_relation, :lookback_relation
+
+ def initialize(grammar, warning, trace_state: false)
+ @grammar = grammar
+ @warning = warning
+ @trace_state = trace_state
+
+ @states = []
+
+ # `DR(p, A) = {t ∈ T | p -(A)-> r -(t)-> }`
+ # where p is state, A is nterm, t is term.
+ #
+ # `@direct_read_sets` is a hash whose
+ # key is [state.id, nterm.token_id],
+ # value is bitmap of term.
+ @direct_read_sets = {}
+
+ # Reads relation on nonterminal transitions (pair of state and nterm)
+ # `(p, A) reads (r, C) iff p -(A)-> r -(C)-> and C =>* ε`
+ # where p, r are state, A, C are nterm.
+ #
+ # `@reads_relation` is a hash whose
+ # key is [state.id, nterm.token_id],
+ # value is array of [state.id, nterm.token_id].
+ @reads_relation = {}
+
+ # `@read_sets` is a hash whose
+ # key is [state.id, nterm.token_id],
+ # value is bitmap of term.
+ @read_sets = {}
+
+ # `(p, A) includes (p', B) iff B -> βAγ, γ =>* ε, p' -(β)-> p`
+ # where p, p' are state, A, B are nterm, β, γ is sequence of symbol.
+ #
+ # `@includes_relation` is a hash whose
+ # key is [state.id, nterm.token_id],
+ # value is array of [state.id, nterm.token_id].
+ @includes_relation = {}
+
+ # `(q, A -> ω) lookback (p, A) iff p -(ω)-> q`
+ # where p, q are state, A -> ω is rule, A is nterm, ω is sequence of symbol.
+ #
+ # `@lookback_relation` is a hash whose
+ # key is [state.id, rule.id],
+ # value is array of [state.id, nterm.token_id].
+ @lookback_relation = {}
+
+ # `@follow_sets` is a hash whose
+ # key is [state.id, rule.id],
+ # value is bitmap of term.
+ @follow_sets = {}
+
+ # `LA(q, A -> ω) = ∪{Follow(p, A) | (q, A -> ω) lookback (p, A)`
+ #
+ # `@la` is a hash whose
+ # key is [state.id, rule.id],
+ # value is bitmap of term.
+ @la = {}
+ end
+
+ def compute
+ # Look Ahead Sets
+ report_duration(:compute_lr0_states) { compute_lr0_states }
+ report_duration(:compute_direct_read_sets) { compute_direct_read_sets }
+ report_duration(:compute_reads_relation) { compute_reads_relation }
+ report_duration(:compute_read_sets) { compute_read_sets }
+ report_duration(:compute_includes_relation) { compute_includes_relation }
+ report_duration(:compute_lookback_relation) { compute_lookback_relation }
+ report_duration(:compute_follow_sets) { compute_follow_sets }
+ report_duration(:compute_look_ahead_sets) { compute_look_ahead_sets }
+
+ # Conflicts
+ report_duration(:compute_conflicts) { compute_conflicts }
+
+ report_duration(:compute_default_reduction) { compute_default_reduction }
+
+ check_conflicts
+ end
+
+ def reporter
+ StatesReporter.new(self)
+ end
+
+ def states_count
+ @states.count
+ end
+
+ def direct_read_sets
+ h = {}
+
+ @direct_read_sets.each do |k, v|
+ h[k] = bitmap_to_terms(v)
+ end
+
+ return h
+ end
+
+ def read_sets
+ h = {}
+
+ @read_sets.each do |k, v|
+ h[k] = bitmap_to_terms(v)
+ end
+
+ return h
+ end
+
+ def follow_sets
+ h = {}
+
+ @follow_sets.each do |k, v|
+ h[k] = bitmap_to_terms(v)
+ end
+
+ return h
+ end
+
+ def la
+ h = {}
+
+ @la.each do |k, v|
+ h[k] = bitmap_to_terms(v)
+ end
+
+ return h
+ end
+
+ private
+
+ def sr_conflicts
+ @states.flat_map(&:sr_conflicts)
+ end
+
+ def rr_conflicts
+ @states.flat_map(&:rr_conflicts)
+ end
+
+ def initial_attrs
+ h = {}
+
+ attrs.each do |attr|
+ h[attr.id] = false
+ end
+
+ h
+ end
+
+ def trace_state
+ if @trace_state
+ yield STDERR
+ end
+ end
+
+ def create_state(accessing_symbol, kernels, states_creted)
+ # A item can appear in some states,
+ # so need to use `kernels` (not `kernels.first`) as a key.
+ #
+ # For example...
+ #
+ # %%
+ # program: '+' strings_1
+ # | '-' strings_2
+ # ;
+ #
+ # strings_1: string_1
+ # ;
+ #
+ # strings_2: string_1
+ # | string_2
+ # ;
+ #
+ # string_1: string
+ # ;
+ #
+ # string_2: string '+'
+ # ;
+ #
+ # string: tSTRING
+ # ;
+ # %%
+ #
+ # For these grammar, there are 2 states
+ #
+ # State A
+ # string_1: string •
+ #
+ # State B
+ # string_1: string •
+ # string_2: string • '+'
+ #
+ return [states_creted[kernels], false] if states_creted[kernels]
+
+ state = State.new(@states.count, accessing_symbol, kernels)
+ @states << state
+ states_creted[kernels] = state
+
+ return [state, true]
+ end
+
+ def setup_state(state)
+ # closure
+ closure = []
+ visited = {}
+ queued = {}
+ items = state.kernels.dup
+
+ items.each do |item|
+ queued[item] = true
+ end
+
+ while (item = items.shift) do
+ visited[item] = true
+
+ if (sym = item.next_sym) && sym.nterm?
+ @grammar.find_rules_by_symbol!(sym).each do |rule|
+ i = Item.new(rule: rule, position: 0)
+ next if queued[i]
+ closure << i
+ items << i
+ queued[i] = true
+ end
+ end
+ end
+
+ state.closure = closure.sort_by {|i| i.rule.id }
+
+ # Trace
+ trace_state do |out|
+ out << "Closure: input\n"
+ state.kernels.each do |item|
+ out << " #{item.display_rest}\n"
+ end
+ out << "\n\n"
+ out << "Closure: output\n"
+ state.items.each do |item|
+ out << " #{item.display_rest}\n"
+ end
+ out << "\n\n"
+ end
+
+ # shift & reduce
+ state.compute_shifts_reduces
+ end
+
+ def enqueue_state(states, state)
+ # Trace
+ previous = state.kernels.first.previous_sym
+ trace_state do |out|
+ out << sprintf("state_list_append (state = %d, symbol = %d (%s))",
+ @states.count, previous.number, previous.display_name)
+ end
+
+ states << state
+ end
+
+ def compute_lr0_states
+ # State queue
+ states = []
+ states_creted = {}
+
+ state, _ = create_state(symbols.first, [Item.new(rule: @grammar.rules.first, position: 0)], states_creted)
+ enqueue_state(states, state)
+
+ while (state = states.shift) do
+ # Trace
+ #
+ # Bison 3.8.2 renders "(reached by "end-of-input")" for State 0 but
+ # I think it is not correct...
+ previous = state.kernels.first.previous_sym
+ trace_state do |out|
+ out << "Processing state #{state.id} (reached by #{previous.display_name})\n"
+ end
+
+ setup_state(state)
+
+ state.shifts.each do |shift|
+ new_state, created = create_state(shift.next_sym, shift.next_items, states_creted)
+ state.set_items_to_state(shift.next_items, new_state)
+ enqueue_state(states, new_state) if created
+ end
+ end
+ end
+
+ def nterm_transitions
+ a = []
+
+ @states.each do |state|
+ state.nterm_transitions.each do |shift, next_state|
+ nterm = shift.next_sym
+ a << [state, nterm, next_state]
+ end
+ end
+
+ a
+ end
+
+ def compute_direct_read_sets
+ @states.each do |state|
+ state.nterm_transitions.each do |shift, next_state|
+ nterm = shift.next_sym
+
+ ary = next_state.term_transitions.map do |shift, _|
+ shift.next_sym.number
+ end
+
+ key = [state.id, nterm.token_id]
+ @direct_read_sets[key] = Bitmap.from_array(ary)
+ end
+ end
+ end
+
+ def compute_reads_relation
+ @states.each do |state|
+ state.nterm_transitions.each do |shift, next_state|
+ nterm = shift.next_sym
+ next_state.nterm_transitions.each do |shift2, _next_state2|
+ nterm2 = shift2.next_sym
+ if nterm2.nullable
+ key = [state.id, nterm.token_id]
+ @reads_relation[key] ||= []
+ @reads_relation[key] << [next_state.id, nterm2.token_id]
+ end
+ end
+ end
+ end
+ end
+
+ def compute_read_sets
+ sets = nterm_transitions.map do |state, nterm, next_state|
+ [state.id, nterm.token_id]
+ end
+
+ @read_sets = Digraph.new(sets, @reads_relation, @direct_read_sets).compute
+ end
+
+ # Execute transition of state by symbols
+ # then return final state.
+ def transition(state, symbols)
+ symbols.each do |sym|
+ state = state.transition(sym)
+ end
+
+ state
+ end
+
+ def compute_includes_relation
+ @states.each do |state|
+ state.nterm_transitions.each do |shift, next_state|
+ nterm = shift.next_sym
+ @grammar.find_rules_by_symbol!(nterm).each do |rule|
+ i = rule.rhs.count - 1
+
+ while (i > -1) do
+ sym = rule.rhs[i]
+
+ break if sym.term?
+ state2 = transition(state, rule.rhs[0...i])
+ # p' = state, B = nterm, p = state2, A = sym
+ key = [state2.id, sym.token_id]
+ # TODO: need to omit if state == state2 ?
+ @includes_relation[key] ||= []
+ @includes_relation[key] << [state.id, nterm.token_id]
+ break if !sym.nullable
+ i -= 1
+ end
+ end
+ end
+ end
+ end
+
+ def compute_lookback_relation
+ @states.each do |state|
+ state.nterm_transitions.each do |shift, next_state|
+ nterm = shift.next_sym
+ @grammar.find_rules_by_symbol!(nterm).each do |rule|
+ state2 = transition(state, rule.rhs)
+ # p = state, A = nterm, q = state2, A -> ω = rule
+ key = [state2.id, rule.id]
+ @lookback_relation[key] ||= []
+ @lookback_relation[key] << [state.id, nterm.token_id]
+ end
+ end
+ end
+ end
+
+ def compute_follow_sets
+ sets = nterm_transitions.map do |state, nterm, next_state|
+ [state.id, nterm.token_id]
+ end
+
+ @follow_sets = Digraph.new(sets, @includes_relation, @read_sets).compute
+ end
+
+ def compute_look_ahead_sets
+ @states.each do |state|
+ rules.each do |rule|
+ ary = @lookback_relation[[state.id, rule.id]]
+ next if !ary
+
+ ary.each do |state2_id, nterm_token_id|
+ # q = state, A -> ω = rule, p = state2, A = nterm
+ follows = @follow_sets[[state2_id, nterm_token_id]]
+
+ next if follows == 0
+
+ key = [state.id, rule.id]
+ @la[key] ||= 0
+ look_ahead = @la[key] | follows
+ @la[key] |= look_ahead
+
+ # No risk of conflict when
+ # * the state only has single reduce
+ # * the state only has nterm_transitions (GOTO)
+ next if state.reduces.count == 1 && state.term_transitions.count == 0
+
+ state.set_look_ahead(rule, bitmap_to_terms(look_ahead))
+ end
+ end
+ end
+ end
+
+ def bitmap_to_terms(bit)
+ ary = Bitmap.to_array(bit)
+ ary.map do |i|
+ @grammar.find_symbol_by_number!(i)
+ end
+ end
+
+ def compute_conflicts
+ compute_shift_reduce_conflicts
+ compute_reduce_reduce_conflicts
+ end
+
+ def compute_shift_reduce_conflicts
+ states.each do |state|
+ state.shifts.each do |shift|
+ state.reduces.each do |reduce|
+ sym = shift.next_sym
+
+ next unless reduce.look_ahead
+ next if !reduce.look_ahead.include?(sym)
+
+ # Shift/Reduce conflict
+ shift_prec = sym.precedence
+ reduce_prec = reduce.item.rule.precedence
+
+ # Can resolve only when both have prec
+ unless shift_prec && reduce_prec
+ state.conflicts << State::Conflict.new(symbols: [sym], reduce: reduce, type: :shift_reduce)
+ next
+ end
+
+ case
+ when shift_prec < reduce_prec
+ # Reduce is selected
+ state.resolved_conflicts << State::ResolvedConflict.new(symbol: sym, reduce: reduce, which: :reduce)
+ shift.not_selected = true
+ next
+ when shift_prec > reduce_prec
+ # Shift is selected
+ state.resolved_conflicts << State::ResolvedConflict.new(symbol: sym, reduce: reduce, which: :shift)
+ reduce.add_not_selected_symbol(sym)
+ next
+ end
+
+ # shift_prec == reduce_prec, then check associativity
+ case sym.precedence.type
+ when :right
+ # Shift is selected
+ state.resolved_conflicts << State::ResolvedConflict.new(symbol: sym, reduce: reduce, which: :shift, same_prec: true)
+ reduce.add_not_selected_symbol(sym)
+ next
+ when :left
+ # Reduce is selected
+ state.resolved_conflicts << State::ResolvedConflict.new(symbol: sym, reduce: reduce, which: :reduce, same_prec: true)
+ shift.not_selected = true
+ next
+ when :nonassoc
+ # Can not resolve
+ #
+ # nonassoc creates "run-time" error, precedence creates "compile-time" error.
+ # Then omit both the shift and reduce.
+ #
+ # https://www.gnu.org/software/bison/manual/html_node/Using-Precedence.html
+ state.resolved_conflicts << State::ResolvedConflict.new(symbol: sym, reduce: reduce, which: :error)
+ shift.not_selected = true
+ reduce.add_not_selected_symbol(sym)
+ else
+ raise "Unknown precedence type. #{sym}"
+ end
+ end
+ end
+ end
+ end
+
+ def compute_reduce_reduce_conflicts
+ states.each do |state|
+ a = []
+
+ state.reduces.each do |reduce|
+ next if reduce.look_ahead.nil?
+
+ intersection = a & reduce.look_ahead
+ a += reduce.look_ahead
+
+ if !intersection.empty?
+ state.conflicts << State::Conflict.new(symbols: intersection.dup, reduce: reduce, type: :reduce_reduce)
+ end
+ end
+ end
+ end
+
+ def compute_default_reduction
+ states.each do |state|
+ next if state.reduces.empty?
+ # Do not set, if conflict exist
+ next if !state.conflicts.empty?
+ # Do not set, if shift with `error` exists.
+ next if state.shifts.map(&:next_sym).include?(@grammar.error_symbol)
+
+ state.default_reduction_rule = state.reduces.map do |r|
+ [r.rule, r.rule.id, (r.look_ahead || []).count]
+ end.sort_by do |rule, rule_id, count|
+ [-count, rule_id]
+ end.first.first
+ end
+ end
+
+ def check_conflicts
+ sr_count = sr_conflicts.count
+ rr_count = rr_conflicts.count
+
+ if @grammar.expect
+
+ expected_sr_conflicts = @grammar.expect
+ expected_rr_conflicts = 0
+
+ if expected_sr_conflicts != sr_count
+ @warning.error("shift/reduce conflicts: #{sr_count} found, #{expected_sr_conflicts} expected")
+ end
+
+ if expected_rr_conflicts != rr_count
+ @warning.error("reduce/reduce conflicts: #{rr_count} found, #{expected_rr_conflicts} expected")
+ end
+ else
+ if sr_count != 0
+ @warning.warn("shift/reduce conflicts: #{sr_count} found")
+ end
+
+ if rr_count != 0
+ @warning.warn("reduce/reduce conflicts: #{rr_count} found")
+ end
+ end
+ end
+ end
+end
diff --git a/tool/lrama/lib/lrama/states_reporter.rb b/tool/lrama/lib/lrama/states_reporter.rb
new file mode 100644
index 0000000000..25893e61be
--- /dev/null
+++ b/tool/lrama/lib/lrama/states_reporter.rb
@@ -0,0 +1,310 @@
+module Lrama
+ class StatesReporter
+ include Lrama::Report::Duration
+
+ def initialize(states)
+ @states = states
+ end
+
+ def report(io, **options)
+ report_duration(:report) do
+ _report(io, **options)
+ end
+ end
+
+ private
+
+ def _report(io, grammar: false, states: false, itemsets: false, lookaheads: false, solved: false, verbose: false)
+ # TODO: Unused terms
+ # TODO: Unused rules
+
+ report_conflicts(io)
+ report_grammar(io) if grammar
+ report_states(io, itemsets, lookaheads, solved, verbose)
+ end
+
+ def report_conflicts(io)
+ has_conflict = false
+
+ @states.states.each do |state|
+ messages = []
+ cs = state.conflicts.group_by(&:type)
+ if cs[:shift_reduce]
+ messages << "#{cs[:shift_reduce].count} shift/reduce"
+ end
+
+ if cs[:reduce_reduce]
+ messages << "#{cs[:reduce_reduce].count} reduce/reduce"
+ end
+
+ if !messages.empty?
+ has_conflict = true
+ io << "State #{state.id} conflicts: #{messages.join(', ')}\n"
+ end
+ end
+
+ if has_conflict
+ io << "\n\n"
+ end
+ end
+
+ def report_grammar(io)
+ io << "Grammar\n"
+ last_lhs = nil
+
+ @states.rules.each do |rule|
+ if rule.rhs.empty?
+ r = "ε"
+ else
+ r = rule.rhs.map(&:display_name).join(" ")
+ end
+
+ if rule.lhs == last_lhs
+ io << sprintf("%5d %s| %s\n", rule.id, " " * rule.lhs.display_name.length, r)
+ else
+ io << "\n"
+ io << sprintf("%5d %s: %s\n", rule.id, rule.lhs.display_name, r)
+ end
+
+ last_lhs = rule.lhs
+ end
+ io << "\n\n"
+ end
+
+ def report_states(io, itemsets, lookaheads, solved, verbose)
+ @states.states.each do |state|
+ # Report State
+ io << "State #{state.id}\n\n"
+
+ # Report item
+ last_lhs = nil
+ list = itemsets ? state.items : state.kernels
+ list.sort_by {|i| [i.rule_id, i.position] }.each do |item|
+ rule = item.rule
+ position = item.position
+ if rule.rhs.empty?
+ r = "ε •"
+ else
+ r = rule.rhs.map(&:display_name).insert(position, "•").join(" ")
+ end
+ if rule.lhs == last_lhs
+ l = " " * rule.lhs.id.s_value.length + "|"
+ else
+ l = rule.lhs.id.s_value + ":"
+ end
+ la = ""
+ if lookaheads && item.end_of_rule?
+ reduce = state.find_reduce_by_item!(item)
+ look_ahead = reduce.selected_look_ahead
+ if !look_ahead.empty?
+ la = " [#{look_ahead.map(&:display_name).join(", ")}]"
+ end
+ end
+ last_lhs = rule.lhs
+
+ io << sprintf("%5i %s %s%s\n", rule.id, l, r, la)
+ end
+ io << "\n"
+
+
+ # Report shifts
+ tmp = state.term_transitions.select do |shift, _|
+ !shift.not_selected
+ end.map do |shift, next_state|
+ [shift.next_sym, next_state.id]
+ end
+ max_len = tmp.map(&:first).map(&:display_name).map(&:length).max
+ tmp.each do |term, state_id|
+ io << " #{term.display_name.ljust(max_len)} shift, and go to state #{state_id}\n"
+ end
+ io << "\n" if !tmp.empty?
+
+
+ # Report error caused by %nonassoc
+ nl = false
+ tmp = state.resolved_conflicts.select do |resolved|
+ resolved.which == :error
+ end.map do |error|
+ error.symbol.display_name
+ end
+ max_len = tmp.map(&:length).max
+ tmp.each do |name|
+ nl = true
+ io << " #{name.ljust(max_len)} error (nonassociative)\n"
+ end
+ io << "\n" if !tmp.empty?
+
+
+ # Report reduces
+ nl = false
+ max_len = state.non_default_reduces.flat_map(&:look_ahead).compact.map(&:display_name).map(&:length).max || 0
+ max_len = [max_len, "$default".length].max if state.default_reduction_rule
+ ary = []
+
+ state.non_default_reduces.each do |reduce|
+ reduce.look_ahead.each do |term|
+ ary << [term, reduce]
+ end
+ end
+
+ ary.sort_by do |term, reduce|
+ term.number
+ end.each do |term, reduce|
+ rule = reduce.item.rule
+ io << " #{term.display_name.ljust(max_len)} reduce using rule #{rule.id} (#{rule.lhs.display_name})\n"
+ nl = true
+ end
+
+ if r = state.default_reduction_rule
+ nl = true
+ s = "$default".ljust(max_len)
+
+ if r.initial_rule?
+ io << " #{s} accept\n"
+ else
+ io << " #{s} reduce using rule #{r.id} (#{r.lhs.display_name})\n"
+ end
+ end
+ io << "\n" if nl
+
+
+ # Report nonterminal transitions
+ tmp = []
+ max_len = 0
+ state.nterm_transitions.each do |shift, next_state|
+ nterm = shift.next_sym
+ tmp << [nterm, next_state.id]
+ max_len = [max_len, nterm.id.s_value.length].max
+ end
+ tmp.uniq!
+ tmp.sort_by! do |nterm, state_id|
+ nterm.number
+ end
+ tmp.each do |nterm, state_id|
+ io << " #{nterm.id.s_value.ljust(max_len)} go to state #{state_id}\n"
+ end
+ io << "\n" if !tmp.empty?
+
+
+ if solved
+ # Report conflict resolutions
+ state.resolved_conflicts.each do |resolved|
+ io << " #{resolved.report_message}\n"
+ end
+ io << "\n" if !state.resolved_conflicts.empty?
+ end
+
+
+ if verbose
+ # Report direct_read_sets
+ io << " [Direct Read sets]\n"
+ direct_read_sets = @states.direct_read_sets
+ @states.nterms.each do |nterm|
+ terms = direct_read_sets[[state.id, nterm.token_id]]
+ next if !terms
+ next if terms.empty?
+
+ str = terms.map {|sym| sym.id.s_value }.join(", ")
+ io << " read #{nterm.id.s_value} shift #{str}\n"
+ end
+ io << "\n"
+
+
+ # Reprot reads_relation
+ io << " [Reads Relation]\n"
+ @states.nterms.each do |nterm|
+ a = @states.reads_relation[[state.id, nterm.token_id]]
+ next if !a
+
+ a.each do |state_id2, nterm_id2|
+ n = @states.nterms.find {|n| n.token_id == nterm_id2 }
+ io << " (State #{state_id2}, #{n.id.s_value})\n"
+ end
+ end
+ io << "\n"
+
+
+ # Reprot read_sets
+ io << " [Read sets]\n"
+ read_sets = @states.read_sets
+ @states.nterms.each do |nterm|
+ terms = read_sets[[state.id, nterm.token_id]]
+ next if !terms
+ next if terms.empty?
+
+ terms.each do |sym|
+ io << " #{sym.id.s_value}\n"
+ end
+ end
+ io << "\n"
+
+
+ # Reprot includes_relation
+ io << " [Includes Relation]\n"
+ @states.nterms.each do |nterm|
+ a = @states.includes_relation[[state.id, nterm.token_id]]
+ next if !a
+
+ a.each do |state_id2, nterm_id2|
+ n = @states.nterms.find {|n| n.token_id == nterm_id2 }
+ io << " (State #{state.id}, #{nterm.id.s_value}) -> (State #{state_id2}, #{n.id.s_value})\n"
+ end
+ end
+ io << "\n"
+
+
+ # Report lookback_relation
+ io << " [Lookback Relation]\n"
+ @states.rules.each do |rule|
+ a = @states.lookback_relation[[state.id, rule.id]]
+ next if !a
+
+ a.each do |state_id2, nterm_id2|
+ n = @states.nterms.find {|n| n.token_id == nterm_id2 }
+ io << " (Rule: #{rule.to_s}) -> (State #{state_id2}, #{n.id.s_value})\n"
+ end
+ end
+ io << "\n"
+
+
+ # Reprot follow_sets
+ io << " [Follow sets]\n"
+ follow_sets = @states.follow_sets
+ @states.nterms.each do |nterm|
+ terms = follow_sets[[state.id, nterm.token_id]]
+
+ next if !terms
+
+ terms.each do |sym|
+ io << " #{nterm.id.s_value} -> #{sym.id.s_value}\n"
+ end
+ end
+ io << "\n"
+
+
+ # Report LA
+ io << " [Look-Ahead Sets]\n"
+ tmp = []
+ max_len = 0
+ @states.rules.each do |rule|
+ syms = @states.la[[state.id, rule.id]]
+ next if !syms
+
+ tmp << [rule, syms]
+ max_len = ([max_len] + syms.map {|s| s.id.s_value.length }).max
+ end
+ tmp.each do |rule, syms|
+ syms.each do |sym|
+ io << " #{sym.id.s_value.ljust(max_len)} reduce using rule #{rule.id} (#{rule.lhs.id.s_value})\n"
+ end
+ end
+ io << "\n" if !tmp.empty?
+ end
+
+
+ # End of Report State
+ io << "\n"
+ end
+ end
+ end
+end
diff --git a/tool/lrama/lib/lrama/version.rb b/tool/lrama/lib/lrama/version.rb
new file mode 100644
index 0000000000..2da384bf73
--- /dev/null
+++ b/tool/lrama/lib/lrama/version.rb
@@ -0,0 +1,3 @@
+module Lrama
+ VERSION = "0.4.0".freeze
+end
diff --git a/tool/lrama/lib/lrama/warning.rb b/tool/lrama/lib/lrama/warning.rb
new file mode 100644
index 0000000000..3c99791ebf
--- /dev/null
+++ b/tool/lrama/lib/lrama/warning.rb
@@ -0,0 +1,25 @@
+module Lrama
+ class Warning
+ attr_reader :errors, :warns
+
+ def initialize(out = STDERR)
+ @out = out
+ @errors = []
+ @warns = []
+ end
+
+ def error(message)
+ @out << message << "\n"
+ @errors << message
+ end
+
+ def warn(message)
+ @out << message << "\n"
+ @warns << message
+ end
+
+ def has_error?
+ !@errors.empty?
+ end
+ end
+end
diff --git a/tool/lrama/template/bison/yacc.c b/tool/lrama/template/bison/yacc.c
new file mode 100644
index 0000000000..b4489966ce
--- /dev/null
+++ b/tool/lrama/template/bison/yacc.c
@@ -0,0 +1,1743 @@
+<%# b4_generated_by -%>
+/* A Bison parser, made by GNU Bison 3.8.2. */
+
+<%# b4_copyright -%>
+/* Bison implementation for Yacc-like parsers in C
+
+ Copyright (C) 1984, 1989-1990, 2000-2015, 2018-2021 Free Software Foundation,
+ Inc.
+
+ This program is free software: you can redistribute it and/or modify
+ it under the terms of the GNU General Public License as published by
+ the Free Software Foundation, either version 3 of the License, or
+ (at your option) any later version.
+
+ This program is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ GNU General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with this program. If not, see <https://www.gnu.org/licenses/>. */
+
+/* As a special exception, you may create a larger work that contains
+ part or all of the Bison parser skeleton and distribute that work
+ under terms of your choice, so long as that work isn't itself a
+ parser generator using the skeleton or a modified version thereof
+ as a parser skeleton. Alternatively, if you modify or redistribute
+ the parser skeleton itself, you may (at your option) remove this
+ special exception, which will cause the skeleton and the resulting
+ Bison output files to be licensed under the GNU General Public
+ License without this special exception.
+
+ This special exception was added by the Free Software Foundation in
+ version 2.2 of Bison. */
+
+/* C LALR(1) parser skeleton written by Richard Stallman, by
+ simplifying the original so-called "semantic" parser. */
+
+<%# b4_disclaimer -%>
+/* DO NOT RELY ON FEATURES THAT ARE NOT DOCUMENTED in the manual,
+ especially those whose name start with YY_ or yy_. They are
+ private implementation details that can be changed or removed. */
+
+/* All symbols defined below should begin with yy or YY, to avoid
+ infringing on user name space. This should be done even for local
+ variables, as they might otherwise be expanded by user macros.
+ There are some unavoidable exceptions within include files to
+ define necessary library symbols; they are noted "INFRINGES ON
+ USER NAME SPACE" below. */
+
+<%# b4_identification -%>
+/* Identify Bison output, and Bison version. */
+#define YYBISON 30802
+
+/* Bison version string. */
+#define YYBISON_VERSION "3.8.2"
+
+/* Skeleton name. */
+#define YYSKELETON_NAME "<%= output.template_basename %>"
+
+/* Pure parsers. */
+#define YYPURE 1
+
+/* Push parsers. */
+#define YYPUSH 0
+
+/* Pull parsers. */
+#define YYPULL 1
+
+
+
+
+<%# b4_user_pre_prologue -%>
+/* First part of user prologue. */
+#line <%= output.aux.prologue_first_lineno %> "<%= output.grammar_file_path %>"
+
+<%= output.aux.prologue %>
+#line [@oline@] [@ofile@]
+
+<%# b4_cast_define -%>
+# ifndef YY_CAST
+# ifdef __cplusplus
+# define YY_CAST(Type, Val) static_cast<Type> (Val)
+# define YY_REINTERPRET_CAST(Type, Val) reinterpret_cast<Type> (Val)
+# else
+# define YY_CAST(Type, Val) ((Type) (Val))
+# define YY_REINTERPRET_CAST(Type, Val) ((Type) (Val))
+# endif
+# endif
+<%# b4_null_define -%>
+# ifndef YY_NULLPTR
+# if defined __cplusplus
+# if 201103L <= __cplusplus
+# define YY_NULLPTR nullptr
+# else
+# define YY_NULLPTR 0
+# endif
+# else
+# define YY_NULLPTR ((void*)0)
+# endif
+# endif
+
+<%# b4_header_include_if -%>
+/* Use api.header.include to #include this header
+ instead of duplicating it here. */
+<%# b4_shared_declarations -%>
+ <%-# b4_cpp_guard_open([b4_spec_mapped_header_file]) -%>
+ <%- if output.spec_mapped_header_file -%>
+#ifndef <%= output.b4_cpp_guard__b4_spec_mapped_header_file %>
+# define <%= output.b4_cpp_guard__b4_spec_mapped_header_file %>
+ <%- end -%>
+ <%-# b4_declare_yydebug & b4_YYDEBUG_define -%>
+/* Debug traces. */
+#ifndef YYDEBUG
+# define YYDEBUG 0
+#endif
+#if YYDEBUG
+extern int yydebug;
+#endif
+ <%-# b4_percent_code_get([[requires]]). %code is not supported -%>
+
+ <%-# b4_token_enums_defines -%>
+/* Token kinds. */
+#ifndef YYTOKENTYPE
+# define YYTOKENTYPE
+ enum yytokentype
+ {
+<%= output.token_enums -%>
+ };
+ typedef enum yytokentype yytoken_kind_t;
+#endif
+
+ <%-# b4_declare_yylstype -%>
+ <%-# b4_value_type_define -%>
+/* Value type. */
+#if ! defined YYSTYPE && ! defined YYSTYPE_IS_DECLARED
+union YYSTYPE
+{
+#line <%= output.grammar.union.lineno %> "<%= output.grammar_file_path %>"
+<%= output.grammar.union.braces_less_code %>
+#line [@oline@] [@ofile@]
+
+};
+typedef union YYSTYPE YYSTYPE;
+# define YYSTYPE_IS_TRIVIAL 1
+# define YYSTYPE_IS_DECLARED 1
+#endif
+
+ <%-# b4_location_type_define -%>
+/* Location type. */
+#if ! defined YYLTYPE && ! defined YYLTYPE_IS_DECLARED
+typedef struct YYLTYPE YYLTYPE;
+struct YYLTYPE
+{
+ int first_line;
+ int first_column;
+ int last_line;
+ int last_column;
+};
+# define YYLTYPE_IS_DECLARED 1
+# define YYLTYPE_IS_TRIVIAL 1
+#endif
+
+
+
+
+ <%-# b4_declare_yyerror_and_yylex. Not supported -%>
+ <%-# b4_declare_yyparse -%>
+int yyparse (<%= output.parse_param %>);
+
+
+ <%-# b4_percent_code_get([[provides]]). %code is not supported -%>
+ <%-# b4_cpp_guard_close([b4_spec_mapped_header_file]) -%>
+ <%- if output.spec_mapped_header_file -%>
+#endif /* !<%= output.b4_cpp_guard__b4_spec_mapped_header_file %> */
+ <%- end -%>
+<%# b4_declare_symbol_enum -%>
+/* Symbol kind. */
+enum yysymbol_kind_t
+{
+<%= output.symbol_enum -%>
+};
+typedef enum yysymbol_kind_t yysymbol_kind_t;
+
+
+
+
+<%# b4_user_post_prologue -%>
+<%# b4_c99_int_type_define -%>
+#ifdef short
+# undef short
+#endif
+
+/* On compilers that do not define __PTRDIFF_MAX__ etc., make sure
+ <limits.h> and (if available) <stdint.h> are included
+ so that the code can choose integer types of a good width. */
+
+#ifndef __PTRDIFF_MAX__
+# include <limits.h> /* INFRINGES ON USER NAME SPACE */
+# if defined __STDC_VERSION__ && 199901 <= __STDC_VERSION__
+# include <stdint.h> /* INFRINGES ON USER NAME SPACE */
+# define YY_STDINT_H
+# endif
+#endif
+
+/* Narrow types that promote to a signed type and that can represent a
+ signed or unsigned integer of at least N bits. In tables they can
+ save space and decrease cache pressure. Promoting to a signed type
+ helps avoid bugs in integer arithmetic. */
+
+#ifdef __INT_LEAST8_MAX__
+typedef __INT_LEAST8_TYPE__ yytype_int8;
+#elif defined YY_STDINT_H
+typedef int_least8_t yytype_int8;
+#else
+typedef signed char yytype_int8;
+#endif
+
+#ifdef __INT_LEAST16_MAX__
+typedef __INT_LEAST16_TYPE__ yytype_int16;
+#elif defined YY_STDINT_H
+typedef int_least16_t yytype_int16;
+#else
+typedef short yytype_int16;
+#endif
+
+/* Work around bug in HP-UX 11.23, which defines these macros
+ incorrectly for preprocessor constants. This workaround can likely
+ be removed in 2023, as HPE has promised support for HP-UX 11.23
+ (aka HP-UX 11i v2) only through the end of 2022; see Table 2 of
+ <https://h20195.www2.hpe.com/V2/getpdf.aspx/4AA4-7673ENW.pdf>. */
+#ifdef __hpux
+# undef UINT_LEAST8_MAX
+# undef UINT_LEAST16_MAX
+# define UINT_LEAST8_MAX 255
+# define UINT_LEAST16_MAX 65535
+#endif
+
+#if defined __UINT_LEAST8_MAX__ && __UINT_LEAST8_MAX__ <= __INT_MAX__
+typedef __UINT_LEAST8_TYPE__ yytype_uint8;
+#elif (!defined __UINT_LEAST8_MAX__ && defined YY_STDINT_H \
+ && UINT_LEAST8_MAX <= INT_MAX)
+typedef uint_least8_t yytype_uint8;
+#elif !defined __UINT_LEAST8_MAX__ && UCHAR_MAX <= INT_MAX
+typedef unsigned char yytype_uint8;
+#else
+typedef short yytype_uint8;
+#endif
+
+#if defined __UINT_LEAST16_MAX__ && __UINT_LEAST16_MAX__ <= __INT_MAX__
+typedef __UINT_LEAST16_TYPE__ yytype_uint16;
+#elif (!defined __UINT_LEAST16_MAX__ && defined YY_STDINT_H \
+ && UINT_LEAST16_MAX <= INT_MAX)
+typedef uint_least16_t yytype_uint16;
+#elif !defined __UINT_LEAST16_MAX__ && USHRT_MAX <= INT_MAX
+typedef unsigned short yytype_uint16;
+#else
+typedef int yytype_uint16;
+#endif
+
+<%# b4_sizes_types_define -%>
+#ifndef YYPTRDIFF_T
+# if defined __PTRDIFF_TYPE__ && defined __PTRDIFF_MAX__
+# define YYPTRDIFF_T __PTRDIFF_TYPE__
+# define YYPTRDIFF_MAXIMUM __PTRDIFF_MAX__
+# elif defined PTRDIFF_MAX
+# ifndef ptrdiff_t
+# include <stddef.h> /* INFRINGES ON USER NAME SPACE */
+# endif
+# define YYPTRDIFF_T ptrdiff_t
+# define YYPTRDIFF_MAXIMUM PTRDIFF_MAX
+# else
+# define YYPTRDIFF_T long
+# define YYPTRDIFF_MAXIMUM LONG_MAX
+# endif
+#endif
+
+#ifndef YYSIZE_T
+# ifdef __SIZE_TYPE__
+# define YYSIZE_T __SIZE_TYPE__
+# elif defined size_t
+# define YYSIZE_T size_t
+# elif defined __STDC_VERSION__ && 199901 <= __STDC_VERSION__
+# include <stddef.h> /* INFRINGES ON USER NAME SPACE */
+# define YYSIZE_T size_t
+# else
+# define YYSIZE_T unsigned
+# endif
+#endif
+
+#define YYSIZE_MAXIMUM \
+ YY_CAST (YYPTRDIFF_T, \
+ (YYPTRDIFF_MAXIMUM < YY_CAST (YYSIZE_T, -1) \
+ ? YYPTRDIFF_MAXIMUM \
+ : YY_CAST (YYSIZE_T, -1)))
+
+#define YYSIZEOF(X) YY_CAST (YYPTRDIFF_T, sizeof (X))
+
+
+/* Stored state numbers (used for stacks). */
+typedef <%= output.int_type_for([output.yynstates - 1]) %> yy_state_t;
+
+/* State numbers in computations. */
+typedef int yy_state_fast_t;
+
+#ifndef YY_
+# if defined YYENABLE_NLS && YYENABLE_NLS
+# if ENABLE_NLS
+# include <libintl.h> /* INFRINGES ON USER NAME SPACE */
+# define YY_(Msgid) dgettext ("bison-runtime", Msgid)
+# endif
+# endif
+# ifndef YY_
+# define YY_(Msgid) Msgid
+# endif
+#endif
+
+
+<%# b4_attribute_define -%>
+#ifndef YY_ATTRIBUTE_PURE
+# if defined __GNUC__ && 2 < __GNUC__ + (96 <= __GNUC_MINOR__)
+# define YY_ATTRIBUTE_PURE __attribute__ ((__pure__))
+# else
+# define YY_ATTRIBUTE_PURE
+# endif
+#endif
+
+#ifndef YY_ATTRIBUTE_UNUSED
+# if defined __GNUC__ && 2 < __GNUC__ + (7 <= __GNUC_MINOR__)
+# define YY_ATTRIBUTE_UNUSED __attribute__ ((__unused__))
+# else
+# define YY_ATTRIBUTE_UNUSED
+# endif
+#endif
+
+/* Suppress unused-variable warnings by "using" E. */
+#if ! defined lint || defined __GNUC__
+# define YY_USE(E) ((void) (E))
+#else
+# define YY_USE(E) /* empty */
+#endif
+
+/* Suppress an incorrect diagnostic about yylval being uninitialized. */
+#if defined __GNUC__ && ! defined __ICC && 406 <= __GNUC__ * 100 + __GNUC_MINOR__
+# if __GNUC__ * 100 + __GNUC_MINOR__ < 407
+# define YY_IGNORE_MAYBE_UNINITIALIZED_BEGIN \
+ _Pragma ("GCC diagnostic push") \
+ _Pragma ("GCC diagnostic ignored \"-Wuninitialized\"")
+# else
+# define YY_IGNORE_MAYBE_UNINITIALIZED_BEGIN \
+ _Pragma ("GCC diagnostic push") \
+ _Pragma ("GCC diagnostic ignored \"-Wuninitialized\"") \
+ _Pragma ("GCC diagnostic ignored \"-Wmaybe-uninitialized\"")
+# endif
+# define YY_IGNORE_MAYBE_UNINITIALIZED_END \
+ _Pragma ("GCC diagnostic pop")
+#else
+# define YY_INITIAL_VALUE(Value) Value
+#endif
+#ifndef YY_IGNORE_MAYBE_UNINITIALIZED_BEGIN
+# define YY_IGNORE_MAYBE_UNINITIALIZED_BEGIN
+# define YY_IGNORE_MAYBE_UNINITIALIZED_END
+#endif
+#ifndef YY_INITIAL_VALUE
+# define YY_INITIAL_VALUE(Value) /* Nothing. */
+#endif
+
+#if defined __cplusplus && defined __GNUC__ && ! defined __ICC && 6 <= __GNUC__
+# define YY_IGNORE_USELESS_CAST_BEGIN \
+ _Pragma ("GCC diagnostic push") \
+ _Pragma ("GCC diagnostic ignored \"-Wuseless-cast\"")
+# define YY_IGNORE_USELESS_CAST_END \
+ _Pragma ("GCC diagnostic pop")
+#endif
+#ifndef YY_IGNORE_USELESS_CAST_BEGIN
+# define YY_IGNORE_USELESS_CAST_BEGIN
+# define YY_IGNORE_USELESS_CAST_END
+#endif
+
+
+#define YY_ASSERT(E) ((void) (0 && (E)))
+
+#if 1
+
+/* The parser invokes alloca or malloc; define the necessary symbols. */
+
+# ifdef YYSTACK_USE_ALLOCA
+# if YYSTACK_USE_ALLOCA
+# ifdef __GNUC__
+# define YYSTACK_ALLOC __builtin_alloca
+# elif defined __BUILTIN_VA_ARG_INCR
+# include <alloca.h> /* INFRINGES ON USER NAME SPACE */
+# elif defined _AIX
+# define YYSTACK_ALLOC __alloca
+# elif defined _MSC_VER
+# include <malloc.h> /* INFRINGES ON USER NAME SPACE */
+# define alloca _alloca
+# else
+# define YYSTACK_ALLOC alloca
+# if ! defined _ALLOCA_H && ! defined EXIT_SUCCESS
+# include <stdlib.h> /* INFRINGES ON USER NAME SPACE */
+ /* Use EXIT_SUCCESS as a witness for stdlib.h. */
+# ifndef EXIT_SUCCESS
+# define EXIT_SUCCESS 0
+# endif
+# endif
+# endif
+# endif
+# endif
+
+# ifdef YYSTACK_ALLOC
+ /* Pacify GCC's 'empty if-body' warning. */
+# define YYSTACK_FREE(Ptr) do { /* empty */; } while (0)
+# ifndef YYSTACK_ALLOC_MAXIMUM
+ /* The OS might guarantee only one guard page at the bottom of the stack,
+ and a page size can be as small as 4096 bytes. So we cannot safely
+ invoke alloca (N) if N exceeds 4096. Use a slightly smaller number
+ to allow for a few compiler-allocated temporary stack slots. */
+# define YYSTACK_ALLOC_MAXIMUM 4032 /* reasonable circa 2006 */
+# endif
+# else
+# define YYSTACK_ALLOC YYMALLOC
+# define YYSTACK_FREE YYFREE
+# ifndef YYSTACK_ALLOC_MAXIMUM
+# define YYSTACK_ALLOC_MAXIMUM YYSIZE_MAXIMUM
+# endif
+# if (defined __cplusplus && ! defined EXIT_SUCCESS \
+ && ! ((defined YYMALLOC || defined malloc) \
+ && (defined YYFREE || defined free)))
+# include <stdlib.h> /* INFRINGES ON USER NAME SPACE */
+# ifndef EXIT_SUCCESS
+# define EXIT_SUCCESS 0
+# endif
+# endif
+# ifndef YYMALLOC
+# define YYMALLOC malloc
+# if ! defined malloc && ! defined EXIT_SUCCESS
+void *malloc (YYSIZE_T); /* INFRINGES ON USER NAME SPACE */
+# endif
+# endif
+# ifndef YYFREE
+# define YYFREE free
+# if ! defined free && ! defined EXIT_SUCCESS
+void free (void *); /* INFRINGES ON USER NAME SPACE */
+# endif
+# endif
+# endif
+#endif /* 1 */
+
+#if (! defined yyoverflow \
+ && (! defined __cplusplus \
+ || (defined YYLTYPE_IS_TRIVIAL && YYLTYPE_IS_TRIVIAL \
+ && defined YYSTYPE_IS_TRIVIAL && YYSTYPE_IS_TRIVIAL)))
+
+/* A type that is properly aligned for any stack member. */
+union yyalloc
+{
+ yy_state_t yyss_alloc;
+ YYSTYPE yyvs_alloc;
+ YYLTYPE yyls_alloc;
+};
+
+/* The size of the maximum gap between one aligned stack and the next. */
+# define YYSTACK_GAP_MAXIMUM (YYSIZEOF (union yyalloc) - 1)
+
+/* The size of an array large to enough to hold all stacks, each with
+ N elements. */
+# define YYSTACK_BYTES(N) \
+ ((N) * (YYSIZEOF (yy_state_t) + YYSIZEOF (YYSTYPE) \
+ + YYSIZEOF (YYLTYPE)) \
+ + 2 * YYSTACK_GAP_MAXIMUM)
+
+# define YYCOPY_NEEDED 1
+
+/* Relocate STACK from its old location to the new one. The
+ local variables YYSIZE and YYSTACKSIZE give the old and new number of
+ elements in the stack, and YYPTR gives the new location of the
+ stack. Advance YYPTR to a properly aligned location for the next
+ stack. */
+# define YYSTACK_RELOCATE(Stack_alloc, Stack) \
+ do \
+ { \
+ YYPTRDIFF_T yynewbytes; \
+ YYCOPY (&yyptr->Stack_alloc, Stack, yysize); \
+ Stack = &yyptr->Stack_alloc; \
+ yynewbytes = yystacksize * YYSIZEOF (*Stack) + YYSTACK_GAP_MAXIMUM; \
+ yyptr += yynewbytes / YYSIZEOF (*yyptr); \
+ } \
+ while (0)
+
+#endif
+
+#if defined YYCOPY_NEEDED && YYCOPY_NEEDED
+/* Copy COUNT objects from SRC to DST. The source and destination do
+ not overlap. */
+# ifndef YYCOPY
+# if defined __GNUC__ && 1 < __GNUC__
+# define YYCOPY(Dst, Src, Count) \
+ __builtin_memcpy (Dst, Src, YY_CAST (YYSIZE_T, (Count)) * sizeof (*(Src)))
+# else
+# define YYCOPY(Dst, Src, Count) \
+ do \
+ { \
+ YYPTRDIFF_T yyi; \
+ for (yyi = 0; yyi < (Count); yyi++) \
+ (Dst)[yyi] = (Src)[yyi]; \
+ } \
+ while (0)
+# endif
+# endif
+#endif /* !YYCOPY_NEEDED */
+
+/* YYFINAL -- State number of the termination state. */
+#define YYFINAL <%= output.yyfinal %>
+/* YYLAST -- Last index in YYTABLE. */
+#define YYLAST <%= output.yylast %>
+
+/* YYNTOKENS -- Number of terminals. */
+#define YYNTOKENS <%= output.yyntokens %>
+/* YYNNTS -- Number of nonterminals. */
+#define YYNNTS <%= output.yynnts %>
+/* YYNRULES -- Number of rules. */
+#define YYNRULES <%= output.yynrules %>
+/* YYNSTATES -- Number of states. */
+#define YYNSTATES <%= output.yynstates %>
+
+/* YYMAXUTOK -- Last valid token kind. */
+#define YYMAXUTOK <%= output.yymaxutok %>
+
+
+/* YYTRANSLATE(TOKEN-NUM) -- Symbol number corresponding to TOKEN-NUM
+ as returned by yylex, with out-of-bounds checking. */
+#define YYTRANSLATE(YYX) \
+ (0 <= (YYX) && (YYX) <= YYMAXUTOK \
+ ? YY_CAST (yysymbol_kind_t, yytranslate[YYX]) \
+ : YYSYMBOL_YYUNDEF)
+
+/* YYTRANSLATE[TOKEN-NUM] -- Symbol number corresponding to TOKEN-NUM
+ as returned by yylex. */
+static const <%= output.int_type_for(output.context.yytranslate) %> yytranslate[] =
+{
+<%= output.yytranslate %>
+};
+
+#if YYDEBUG
+/* YYRLINE[YYN] -- Source line where rule number YYN was defined. */
+static const <%= output.int_type_for(output.context.yyrline) %> yyrline[] =
+{
+<%= output.yyrline %>
+};
+#endif
+
+/** Accessing symbol of state STATE. */
+#define YY_ACCESSING_SYMBOL(State) YY_CAST (yysymbol_kind_t, yystos[State])
+
+#if 1
+/* The user-facing name of the symbol whose (internal) number is
+ YYSYMBOL. No bounds checking. */
+static const char *yysymbol_name (yysymbol_kind_t yysymbol) YY_ATTRIBUTE_UNUSED;
+
+/* YYTNAME[SYMBOL-NUM] -- String name of the symbol SYMBOL-NUM.
+ First, the terminals, then, starting at YYNTOKENS, nonterminals. */
+static const char *const yytname[] =
+{
+<%= output.yytname %>
+};
+
+static const char *
+yysymbol_name (yysymbol_kind_t yysymbol)
+{
+ return yytname[yysymbol];
+}
+#endif
+
+#define YYPACT_NINF (<%= output.yypact_ninf %>)
+
+#define yypact_value_is_default(Yyn) \
+ <%= output.table_value_equals(output.context.yypact, "Yyn", output.yypact_ninf, "YYPACT_NINF") %>
+
+#define YYTABLE_NINF (<%= output.yytable_ninf %>)
+
+#define yytable_value_is_error(Yyn) \
+ <%= output.table_value_equals(output.context.yytable, "Yyn", output.yytable_ninf, "YYTABLE_NINF") %>
+
+<%# b4_parser_tables_define -%>
+/* YYPACT[STATE-NUM] -- Index in YYTABLE of the portion describing
+ STATE-NUM. */
+static const <%= output.int_type_for(output.context.yypact) %> yypact[] =
+{
+<%= output.int_array_to_string(output.context.yypact) %>
+};
+
+/* YYDEFACT[STATE-NUM] -- Default reduction number in state STATE-NUM.
+ Performed when YYTABLE does not specify something else to do. Zero
+ means the default is an error. */
+static const <%= output.int_type_for(output.context.yydefact) %> yydefact[] =
+{
+<%= output.int_array_to_string(output.context.yydefact) %>
+};
+
+/* YYPGOTO[NTERM-NUM]. */
+static const <%= output.int_type_for(output.context.yypgoto) %> yypgoto[] =
+{
+<%= output.int_array_to_string(output.context.yypgoto) %>
+};
+
+/* YYDEFGOTO[NTERM-NUM]. */
+static const <%= output.int_type_for(output.context.yydefgoto) %> yydefgoto[] =
+{
+<%= output.int_array_to_string(output.context.yydefgoto) %>
+};
+
+/* YYTABLE[YYPACT[STATE-NUM]] -- What to do in state STATE-NUM. If
+ positive, shift that token. If negative, reduce the rule whose
+ number is the opposite. If YYTABLE_NINF, syntax error. */
+static const <%= output.int_type_for(output.context.yytable) %> yytable[] =
+{
+<%= output.int_array_to_string(output.context.yytable) %>
+};
+
+static const <%= output.int_type_for(output.context.yycheck) %> yycheck[] =
+{
+<%= output.int_array_to_string(output.context.yycheck) %>
+};
+
+/* YYSTOS[STATE-NUM] -- The symbol kind of the accessing symbol of
+ state STATE-NUM. */
+static const <%= output.int_type_for(output.context.yystos) %> yystos[] =
+{
+<%= output.int_array_to_string(output.context.yystos) %>
+};
+
+/* YYR1[RULE-NUM] -- Symbol kind of the left-hand side of rule RULE-NUM. */
+static const <%= output.int_type_for(output.context.yyr1) %> yyr1[] =
+{
+<%= output.int_array_to_string(output.context.yyr1) %>
+};
+
+/* YYR2[RULE-NUM] -- Number of symbols on the right-hand side of rule RULE-NUM. */
+static const <%= output.int_type_for(output.context.yyr2) %> yyr2[] =
+{
+<%= output.int_array_to_string(output.context.yyr2) %>
+};
+
+
+enum { YYENOMEM = -2 };
+
+#define yyerrok (yyerrstatus = 0)
+#define yyclearin (yychar = YYEMPTY)
+
+#define YYACCEPT goto yyacceptlab
+#define YYABORT goto yyabortlab
+#define YYERROR goto yyerrorlab
+#define YYNOMEM goto yyexhaustedlab
+
+
+#define YYRECOVERING() (!!yyerrstatus)
+
+#define YYBACKUP(Token, Value) \
+ do \
+ if (yychar == YYEMPTY) \
+ { \
+ yychar = (Token); \
+ yylval = (Value); \
+ YYPOPSTACK (yylen); \
+ yystate = *yyssp; \
+ goto yybackup; \
+ } \
+ else \
+ { \
+ yyerror (<%= output.yyerror_args %>, YY_("syntax error: cannot back up")); \
+ YYERROR; \
+ } \
+ while (0)
+
+/* Backward compatibility with an undocumented macro.
+ Use YYerror or YYUNDEF. */
+#define YYERRCODE YYUNDEF
+
+<%# b4_yylloc_default_define -%>
+/* YYLLOC_DEFAULT -- Set CURRENT to span from RHS[1] to RHS[N].
+ If N is 0, then set CURRENT to the empty location which ends
+ the previous symbol: RHS[0] (always defined). */
+
+#ifndef YYLLOC_DEFAULT
+# define YYLLOC_DEFAULT(Current, Rhs, N) \
+ do \
+ if (N) \
+ { \
+ (Current).first_line = YYRHSLOC (Rhs, 1).first_line; \
+ (Current).first_column = YYRHSLOC (Rhs, 1).first_column; \
+ (Current).last_line = YYRHSLOC (Rhs, N).last_line; \
+ (Current).last_column = YYRHSLOC (Rhs, N).last_column; \
+ } \
+ else \
+ { \
+ (Current).first_line = (Current).last_line = \
+ YYRHSLOC (Rhs, 0).last_line; \
+ (Current).first_column = (Current).last_column = \
+ YYRHSLOC (Rhs, 0).last_column; \
+ } \
+ while (0)
+#endif
+
+#define YYRHSLOC(Rhs, K) ((Rhs)[K])
+
+
+/* Enable debugging if requested. */
+#if YYDEBUG
+
+# ifndef YYFPRINTF
+# include <stdio.h> /* INFRINGES ON USER NAME SPACE */
+# define YYFPRINTF fprintf
+# endif
+
+# define YYDPRINTF(Args) \
+do { \
+ if (yydebug) \
+ YYFPRINTF Args; \
+} while (0)
+
+
+<%# b4_yylocation_print_define -%>
+/* YYLOCATION_PRINT -- Print the location on the stream.
+ This macro was not mandated originally: define only if we know
+ we won't break user code: when these are the locations we know. */
+
+# ifndef YYLOCATION_PRINT
+
+# if defined YY_LOCATION_PRINT
+
+ /* Temporary convenience wrapper in case some people defined the
+ undocumented and private YY_LOCATION_PRINT macros. */
+# define YYLOCATION_PRINT(File, Loc) YY_LOCATION_PRINT(File, *(Loc))
+
+# elif defined YYLTYPE_IS_TRIVIAL && YYLTYPE_IS_TRIVIAL
+
+/* Print *YYLOCP on YYO. Private, do not rely on its existence. */
+
+YY_ATTRIBUTE_UNUSED
+static int
+yy_location_print_ (FILE *yyo, YYLTYPE const * const yylocp)
+{
+ int res = 0;
+ int end_col = 0 != yylocp->last_column ? yylocp->last_column - 1 : 0;
+ if (0 <= yylocp->first_line)
+ {
+ res += YYFPRINTF (yyo, "%d", yylocp->first_line);
+ if (0 <= yylocp->first_column)
+ res += YYFPRINTF (yyo, ".%d", yylocp->first_column);
+ }
+ if (0 <= yylocp->last_line)
+ {
+ if (yylocp->first_line < yylocp->last_line)
+ {
+ res += YYFPRINTF (yyo, "-%d", yylocp->last_line);
+ if (0 <= end_col)
+ res += YYFPRINTF (yyo, ".%d", end_col);
+ }
+ else if (0 <= end_col && yylocp->first_column < end_col)
+ res += YYFPRINTF (yyo, "-%d", end_col);
+ }
+ return res;
+}
+
+# define YYLOCATION_PRINT yy_location_print_
+
+ /* Temporary convenience wrapper in case some people defined the
+ undocumented and private YY_LOCATION_PRINT macros. */
+# define YY_LOCATION_PRINT(File, Loc) YYLOCATION_PRINT(File, &(Loc))
+
+# else
+
+# define YYLOCATION_PRINT(File, Loc) ((void) 0)
+ /* Temporary convenience wrapper in case some people defined the
+ undocumented and private YY_LOCATION_PRINT macros. */
+# define YY_LOCATION_PRINT YYLOCATION_PRINT
+
+# endif
+# endif /* !defined YYLOCATION_PRINT */
+
+
+# define YY_SYMBOL_PRINT(Title, Kind, Value, Location) \
+do { \
+ if (yydebug) \
+ { \
+ YYFPRINTF (stderr, "%s ", Title); \
+ yy_symbol_print (stderr, \
+ Kind, Value, Location, p); \
+ YYFPRINTF (stderr, "\n"); \
+ } \
+} while (0)
+
+
+<%# b4_yy_symbol_print_define -%>
+/*-----------------------------------.
+| Print this symbol's value on YYO. |
+`-----------------------------------*/
+
+static void
+yy_symbol_value_print (FILE *yyo,
+ yysymbol_kind_t yykind, YYSTYPE const * const yyvaluep, YYLTYPE const * const yylocationp<%= output.user_formals %>)
+{
+ FILE *yyoutput = yyo;
+<%= output.parse_param_use("yyoutput", "yylocationp") %>
+ if (!yyvaluep)
+ return;
+ YY_IGNORE_MAYBE_UNINITIALIZED_BEGIN
+<%# b4_symbol_actions(printer) -%>
+switch (yykind)
+ {
+<%= output.symbol_actions_for_printer -%>
+ default:
+ break;
+ }
+ YY_IGNORE_MAYBE_UNINITIALIZED_END
+}
+
+
+/*---------------------------.
+| Print this symbol on YYO. |
+`---------------------------*/
+
+static void
+yy_symbol_print (FILE *yyo,
+ yysymbol_kind_t yykind, YYSTYPE const * const yyvaluep, YYLTYPE const * const yylocationp<%= output.user_formals %>)
+{
+ YYFPRINTF (yyo, "%s %s (",
+ yykind < YYNTOKENS ? "token" : "nterm", yysymbol_name (yykind));
+
+ YYLOCATION_PRINT (yyo, yylocationp);
+ YYFPRINTF (yyo, ": ");
+ yy_symbol_value_print (yyo, yykind, yyvaluep, yylocationp, p);
+ YYFPRINTF (yyo, ")");
+}
+
+/*------------------------------------------------------------------.
+| yy_stack_print -- Print the state stack from its BOTTOM up to its |
+| TOP (included). |
+`------------------------------------------------------------------*/
+
+static void
+yy_stack_print (yy_state_t *yybottom, yy_state_t *yytop)
+{
+ YYFPRINTF (stderr, "Stack now");
+ for (; yybottom <= yytop; yybottom++)
+ {
+ int yybot = *yybottom;
+ YYFPRINTF (stderr, " %d", yybot);
+ }
+ YYFPRINTF (stderr, "\n");
+}
+
+# define YY_STACK_PRINT(Bottom, Top) \
+do { \
+ if (yydebug) \
+ yy_stack_print ((Bottom), (Top)); \
+} while (0)
+
+
+/*------------------------------------------------.
+| Report that the YYRULE is going to be reduced. |
+`------------------------------------------------*/
+
+static void
+yy_reduce_print (yy_state_t *yyssp, YYSTYPE *yyvsp, YYLTYPE *yylsp,
+ int yyrule<%= output.user_formals %>)
+{
+ int yylno = yyrline[yyrule];
+ int yynrhs = yyr2[yyrule];
+ int yyi;
+ YYFPRINTF (stderr, "Reducing stack by rule %d (line %d):\n",
+ yyrule - 1, yylno);
+ /* The symbols being reduced. */
+ for (yyi = 0; yyi < yynrhs; yyi++)
+ {
+ YYFPRINTF (stderr, " $%d = ", yyi + 1);
+ yy_symbol_print (stderr,
+ YY_ACCESSING_SYMBOL (+yyssp[yyi + 1 - yynrhs]),
+ &yyvsp[(yyi + 1) - (yynrhs)],
+ &(yylsp[(yyi + 1) - (yynrhs)]), p);
+ YYFPRINTF (stderr, "\n");
+ }
+}
+
+# define YY_REDUCE_PRINT(Rule) \
+do { \
+ if (yydebug) \
+ yy_reduce_print (yyssp, yyvsp, yylsp, Rule, p); \
+} while (0)
+
+/* Nonzero means print parse trace. It is left uninitialized so that
+ multiple parsers can coexist. */
+int yydebug;
+#else /* !YYDEBUG */
+# define YYDPRINTF(Args) ((void) 0)
+# define YY_SYMBOL_PRINT(Title, Kind, Value, Location)
+# define YY_STACK_PRINT(Bottom, Top)
+# define YY_REDUCE_PRINT(Rule)
+#endif /* !YYDEBUG */
+
+
+/* YYINITDEPTH -- initial size of the parser's stacks. */
+#ifndef YYINITDEPTH
+# define YYINITDEPTH 200
+#endif
+
+/* YYMAXDEPTH -- maximum size the stacks can grow to (effective only
+ if the built-in stack extension method is used).
+
+ Do not make this value too large; the results are undefined if
+ YYSTACK_ALLOC_MAXIMUM < YYSTACK_BYTES (YYMAXDEPTH)
+ evaluated with infinite-precision integer arithmetic. */
+
+#ifndef YYMAXDEPTH
+# define YYMAXDEPTH 10000
+#endif
+
+
+/* Context of a parse error. */
+typedef struct
+{
+ yy_state_t *yyssp;
+ yysymbol_kind_t yytoken;
+ YYLTYPE *yylloc;
+} yypcontext_t;
+
+/* Put in YYARG at most YYARGN of the expected tokens given the
+ current YYCTX, and return the number of tokens stored in YYARG. If
+ YYARG is null, return the number of expected tokens (guaranteed to
+ be less than YYNTOKENS). Return YYENOMEM on memory exhaustion.
+ Return 0 if there are more than YYARGN expected tokens, yet fill
+ YYARG up to YYARGN. */
+static int
+yypcontext_expected_tokens (const yypcontext_t *yyctx,
+ yysymbol_kind_t yyarg[], int yyargn)
+{
+ /* Actual size of YYARG. */
+ int yycount = 0;
+ int yyn = yypact[+*yyctx->yyssp];
+ if (!yypact_value_is_default (yyn))
+ {
+ /* Start YYX at -YYN if negative to avoid negative indexes in
+ YYCHECK. In other words, skip the first -YYN actions for
+ this state because they are default actions. */
+ int yyxbegin = yyn < 0 ? -yyn : 0;
+ /* Stay within bounds of both yycheck and yytname. */
+ int yychecklim = YYLAST - yyn + 1;
+ int yyxend = yychecklim < YYNTOKENS ? yychecklim : YYNTOKENS;
+ int yyx;
+ for (yyx = yyxbegin; yyx < yyxend; ++yyx)
+ if (yycheck[yyx + yyn] == yyx && yyx != YYSYMBOL_YYerror
+ && !yytable_value_is_error (yytable[yyx + yyn]))
+ {
+ if (!yyarg)
+ ++yycount;
+ else if (yycount == yyargn)
+ return 0;
+ else
+ yyarg[yycount++] = YY_CAST (yysymbol_kind_t, yyx);
+ }
+ }
+ if (yyarg && yycount == 0 && 0 < yyargn)
+ yyarg[0] = YYSYMBOL_YYEMPTY;
+ return yycount;
+}
+
+
+
+
+#ifndef yystrlen
+# if defined __GLIBC__ && defined _STRING_H
+# define yystrlen(S) (YY_CAST (YYPTRDIFF_T, strlen (S)))
+# else
+/* Return the length of YYSTR. */
+static YYPTRDIFF_T
+yystrlen (const char *yystr)
+{
+ YYPTRDIFF_T yylen;
+ for (yylen = 0; yystr[yylen]; yylen++)
+ continue;
+ return yylen;
+}
+# endif
+#endif
+
+#ifndef yystpcpy
+# if defined __GLIBC__ && defined _STRING_H && defined _GNU_SOURCE
+# define yystpcpy stpcpy
+# else
+/* Copy YYSRC to YYDEST, returning the address of the terminating '\0' in
+ YYDEST. */
+static char *
+yystpcpy (char *yydest, const char *yysrc)
+{
+ char *yyd = yydest;
+ const char *yys = yysrc;
+
+ while ((*yyd++ = *yys++) != '\0')
+ continue;
+
+ return yyd - 1;
+}
+# endif
+#endif
+
+#ifndef yytnamerr
+/* Copy to YYRES the contents of YYSTR after stripping away unnecessary
+ quotes and backslashes, so that it's suitable for yyerror. The
+ heuristic is that double-quoting is unnecessary unless the string
+ contains an apostrophe, a comma, or backslash (other than
+ backslash-backslash). YYSTR is taken from yytname. If YYRES is
+ null, do not copy; instead, return the length of what the result
+ would have been. */
+static YYPTRDIFF_T
+yytnamerr (char *yyres, const char *yystr)
+{
+ if (*yystr == '"')
+ {
+ YYPTRDIFF_T yyn = 0;
+ char const *yyp = yystr;
+ for (;;)
+ switch (*++yyp)
+ {
+ case '\'':
+ case ',':
+ goto do_not_strip_quotes;
+
+ case '\\':
+ if (*++yyp != '\\')
+ goto do_not_strip_quotes;
+ else
+ goto append;
+
+ append:
+ default:
+ if (yyres)
+ yyres[yyn] = *yyp;
+ yyn++;
+ break;
+
+ case '"':
+ if (yyres)
+ yyres[yyn] = '\0';
+ return yyn;
+ }
+ do_not_strip_quotes: ;
+ }
+
+ if (yyres)
+ return yystpcpy (yyres, yystr) - yyres;
+ else
+ return yystrlen (yystr);
+}
+#endif
+
+
+static int
+yy_syntax_error_arguments (const yypcontext_t *yyctx,
+ yysymbol_kind_t yyarg[], int yyargn)
+{
+ /* Actual size of YYARG. */
+ int yycount = 0;
+ /* There are many possibilities here to consider:
+ - If this state is a consistent state with a default action, then
+ the only way this function was invoked is if the default action
+ is an error action. In that case, don't check for expected
+ tokens because there are none.
+ - The only way there can be no lookahead present (in yychar) is if
+ this state is a consistent state with a default action. Thus,
+ detecting the absence of a lookahead is sufficient to determine
+ that there is no unexpected or expected token to report. In that
+ case, just report a simple "syntax error".
+ - Don't assume there isn't a lookahead just because this state is a
+ consistent state with a default action. There might have been a
+ previous inconsistent state, consistent state with a non-default
+ action, or user semantic action that manipulated yychar.
+ - Of course, the expected token list depends on states to have
+ correct lookahead information, and it depends on the parser not
+ to perform extra reductions after fetching a lookahead from the
+ scanner and before detecting a syntax error. Thus, state merging
+ (from LALR or IELR) and default reductions corrupt the expected
+ token list. However, the list is correct for canonical LR with
+ one exception: it will still contain any token that will not be
+ accepted due to an error action in a later state.
+ */
+ if (yyctx->yytoken != YYSYMBOL_YYEMPTY)
+ {
+ int yyn;
+ if (yyarg)
+ yyarg[yycount] = yyctx->yytoken;
+ ++yycount;
+ yyn = yypcontext_expected_tokens (yyctx,
+ yyarg ? yyarg + 1 : yyarg, yyargn - 1);
+ if (yyn == YYENOMEM)
+ return YYENOMEM;
+ else
+ yycount += yyn;
+ }
+ return yycount;
+}
+
+/* Copy into *YYMSG, which is of size *YYMSG_ALLOC, an error message
+ about the unexpected token YYTOKEN for the state stack whose top is
+ YYSSP.
+
+ Return 0 if *YYMSG was successfully written. Return -1 if *YYMSG is
+ not large enough to hold the message. In that case, also set
+ *YYMSG_ALLOC to the required number of bytes. Return YYENOMEM if the
+ required number of bytes is too large to store. */
+static int
+yysyntax_error (YYPTRDIFF_T *yymsg_alloc, char **yymsg,
+ const yypcontext_t *yyctx)
+{
+ enum { YYARGS_MAX = 5 };
+ /* Internationalized format string. */
+ const char *yyformat = YY_NULLPTR;
+ /* Arguments of yyformat: reported tokens (one for the "unexpected",
+ one per "expected"). */
+ yysymbol_kind_t yyarg[YYARGS_MAX];
+ /* Cumulated lengths of YYARG. */
+ YYPTRDIFF_T yysize = 0;
+
+ /* Actual size of YYARG. */
+ int yycount = yy_syntax_error_arguments (yyctx, yyarg, YYARGS_MAX);
+ if (yycount == YYENOMEM)
+ return YYENOMEM;
+
+ switch (yycount)
+ {
+#define YYCASE_(N, S) \
+ case N: \
+ yyformat = S; \
+ break
+ default: /* Avoid compiler warnings. */
+ YYCASE_(0, YY_("syntax error"));
+ YYCASE_(1, YY_("syntax error, unexpected %s"));
+ YYCASE_(2, YY_("syntax error, unexpected %s, expecting %s"));
+ YYCASE_(3, YY_("syntax error, unexpected %s, expecting %s or %s"));
+ YYCASE_(4, YY_("syntax error, unexpected %s, expecting %s or %s or %s"));
+ YYCASE_(5, YY_("syntax error, unexpected %s, expecting %s or %s or %s or %s"));
+#undef YYCASE_
+ }
+
+ /* Compute error message size. Don't count the "%s"s, but reserve
+ room for the terminator. */
+ yysize = yystrlen (yyformat) - 2 * yycount + 1;
+ {
+ int yyi;
+ for (yyi = 0; yyi < yycount; ++yyi)
+ {
+ YYPTRDIFF_T yysize1
+ = yysize + yytnamerr (YY_NULLPTR, yytname[yyarg[yyi]]);
+ if (yysize <= yysize1 && yysize1 <= YYSTACK_ALLOC_MAXIMUM)
+ yysize = yysize1;
+ else
+ return YYENOMEM;
+ }
+ }
+
+ if (*yymsg_alloc < yysize)
+ {
+ *yymsg_alloc = 2 * yysize;
+ if (! (yysize <= *yymsg_alloc
+ && *yymsg_alloc <= YYSTACK_ALLOC_MAXIMUM))
+ *yymsg_alloc = YYSTACK_ALLOC_MAXIMUM;
+ return -1;
+ }
+
+ /* Avoid sprintf, as that infringes on the user's name space.
+ Don't have undefined behavior even if the translation
+ produced a string with the wrong number of "%s"s. */
+ {
+ char *yyp = *yymsg;
+ int yyi = 0;
+ while ((*yyp = *yyformat) != '\0')
+ if (*yyp == '%' && yyformat[1] == 's' && yyi < yycount)
+ {
+ yyp += yytnamerr (yyp, yytname[yyarg[yyi++]]);
+ yyformat += 2;
+ }
+ else
+ {
+ ++yyp;
+ ++yyformat;
+ }
+ }
+ return 0;
+}
+
+<%# b4_yydestruct_define %>
+/*-----------------------------------------------.
+| Release the memory associated to this symbol. |
+`-----------------------------------------------*/
+
+static void
+yydestruct (const char *yymsg,
+ yysymbol_kind_t yykind, YYSTYPE *yyvaluep, YYLTYPE *yylocationp<%= output.user_formals %>)
+{
+<%= output.parse_param_use("yyvaluep", "yylocationp") %>
+ if (!yymsg)
+ yymsg = "Deleting";
+ YY_SYMBOL_PRINT (yymsg, yykind, yyvaluep, yylocationp);
+
+ YY_IGNORE_MAYBE_UNINITIALIZED_BEGIN
+ YY_USE (yykind);
+ YY_IGNORE_MAYBE_UNINITIALIZED_END
+}
+
+
+
+
+
+
+/*----------.
+| yyparse. |
+`----------*/
+
+int
+yyparse (<%= output.parse_param %>)
+{
+<%# b4_declare_scanner_communication_variables -%>
+/* Lookahead token kind. */
+int yychar;
+
+
+/* The semantic value of the lookahead symbol. */
+/* Default value used for initialization, for pacifying older GCCs
+ or non-GCC compilers. */
+YY_INITIAL_VALUE (static YYSTYPE yyval_default;)
+YYSTYPE yylval YY_INITIAL_VALUE (= yyval_default);
+
+/* Location data for the lookahead symbol. */
+static YYLTYPE yyloc_default
+# if defined YYLTYPE_IS_TRIVIAL && YYLTYPE_IS_TRIVIAL
+ = { 1, 1, 1, 1 }
+# endif
+;
+YYLTYPE yylloc = yyloc_default;
+
+<%# b4_declare_parser_state_variables -%>
+ /* Number of syntax errors so far. */
+ int yynerrs = 0;
+
+ yy_state_fast_t yystate = 0;
+ /* Number of tokens to shift before error messages enabled. */
+ int yyerrstatus = 0;
+
+ /* Refer to the stacks through separate pointers, to allow yyoverflow
+ to reallocate them elsewhere. */
+
+ /* Their size. */
+ YYPTRDIFF_T yystacksize = YYINITDEPTH;
+
+ /* The state stack: array, bottom, top. */
+ yy_state_t yyssa[YYINITDEPTH];
+ yy_state_t *yyss = yyssa;
+ yy_state_t *yyssp = yyss;
+
+ /* The semantic value stack: array, bottom, top. */
+ YYSTYPE yyvsa[YYINITDEPTH];
+ YYSTYPE *yyvs = yyvsa;
+ YYSTYPE *yyvsp = yyvs;
+
+ /* The location stack: array, bottom, top. */
+ YYLTYPE yylsa[YYINITDEPTH];
+ YYLTYPE *yyls = yylsa;
+ YYLTYPE *yylsp = yyls;
+
+ int yyn;
+ /* The return value of yyparse. */
+ int yyresult;
+ /* Lookahead symbol kind. */
+ yysymbol_kind_t yytoken = YYSYMBOL_YYEMPTY;
+ /* The variables used to return semantic value and location from the
+ action routines. */
+ YYSTYPE yyval;
+ YYLTYPE yyloc;
+
+ /* The locations where the error started and ended. */
+ YYLTYPE yyerror_range[3];
+
+ /* Buffer for error messages, and its allocated size. */
+ char yymsgbuf[128];
+ char *yymsg = yymsgbuf;
+ YYPTRDIFF_T yymsg_alloc = sizeof yymsgbuf;
+
+#define YYPOPSTACK(N) (yyvsp -= (N), yyssp -= (N), yylsp -= (N))
+
+ /* The number of symbols on the RHS of the reduced rule.
+ Keep to zero when no symbol should be popped. */
+ int yylen = 0;
+
+ YYDPRINTF ((stderr, "Starting parse\n"));
+
+ yychar = YYEMPTY; /* Cause a token to be read. */
+
+
+<%# b4_user_initial_action -%>
+<%= output.user_initial_action("/* User initialization code. */") %>
+#line [@oline@] [@ofile@]
+
+ yylsp[0] = yylloc;
+ goto yysetstate;
+
+
+/*------------------------------------------------------------.
+| yynewstate -- push a new state, which is found in yystate. |
+`------------------------------------------------------------*/
+yynewstate:
+ /* In all cases, when you get here, the value and location stacks
+ have just been pushed. So pushing a state here evens the stacks. */
+ yyssp++;
+
+
+/*--------------------------------------------------------------------.
+| yysetstate -- set current state (the top of the stack) to yystate. |
+`--------------------------------------------------------------------*/
+yysetstate:
+ YYDPRINTF ((stderr, "Entering state %d\n", yystate));
+ YY_ASSERT (0 <= yystate && yystate < YYNSTATES);
+ YY_IGNORE_USELESS_CAST_BEGIN
+ *yyssp = YY_CAST (yy_state_t, yystate);
+ YY_IGNORE_USELESS_CAST_END
+ YY_STACK_PRINT (yyss, yyssp);
+
+ if (yyss + yystacksize - 1 <= yyssp)
+#if !defined yyoverflow && !defined YYSTACK_RELOCATE
+ YYNOMEM;
+#else
+ {
+ /* Get the current used size of the three stacks, in elements. */
+ YYPTRDIFF_T yysize = yyssp - yyss + 1;
+
+# if defined yyoverflow
+ {
+ /* Give user a chance to reallocate the stack. Use copies of
+ these so that the &'s don't force the real ones into
+ memory. */
+ yy_state_t *yyss1 = yyss;
+ YYSTYPE *yyvs1 = yyvs;
+ YYLTYPE *yyls1 = yyls;
+
+ /* Each stack pointer address is followed by the size of the
+ data in use in that stack, in bytes. This used to be a
+ conditional around just the two extra args, but that might
+ be undefined if yyoverflow is a macro. */
+ yyoverflow (YY_("memory exhausted"),
+ &yyss1, yysize * YYSIZEOF (*yyssp),
+ &yyvs1, yysize * YYSIZEOF (*yyvsp),
+ &yyls1, yysize * YYSIZEOF (*yylsp),
+ &yystacksize);
+ yyss = yyss1;
+ yyvs = yyvs1;
+ yyls = yyls1;
+ }
+# else /* defined YYSTACK_RELOCATE */
+ /* Extend the stack our own way. */
+ if (YYMAXDEPTH <= yystacksize)
+ YYNOMEM;
+ yystacksize *= 2;
+ if (YYMAXDEPTH < yystacksize)
+ yystacksize = YYMAXDEPTH;
+
+ {
+ yy_state_t *yyss1 = yyss;
+ union yyalloc *yyptr =
+ YY_CAST (union yyalloc *,
+ YYSTACK_ALLOC (YY_CAST (YYSIZE_T, YYSTACK_BYTES (yystacksize))));
+ if (! yyptr)
+ YYNOMEM;
+ YYSTACK_RELOCATE (yyss_alloc, yyss);
+ YYSTACK_RELOCATE (yyvs_alloc, yyvs);
+ YYSTACK_RELOCATE (yyls_alloc, yyls);
+# undef YYSTACK_RELOCATE
+ if (yyss1 != yyssa)
+ YYSTACK_FREE (yyss1);
+ }
+# endif
+
+ yyssp = yyss + yysize - 1;
+ yyvsp = yyvs + yysize - 1;
+ yylsp = yyls + yysize - 1;
+
+ YY_IGNORE_USELESS_CAST_BEGIN
+ YYDPRINTF ((stderr, "Stack size increased to %ld\n",
+ YY_CAST (long, yystacksize)));
+ YY_IGNORE_USELESS_CAST_END
+
+ if (yyss + yystacksize - 1 <= yyssp)
+ YYABORT;
+ }
+#endif /* !defined yyoverflow && !defined YYSTACK_RELOCATE */
+
+
+ if (yystate == YYFINAL)
+ YYACCEPT;
+
+ goto yybackup;
+
+
+/*-----------.
+| yybackup. |
+`-----------*/
+yybackup:
+ /* Do appropriate processing given the current state. Read a
+ lookahead token if we need one and don't already have one. */
+
+ /* First try to decide what to do without reference to lookahead token. */
+ yyn = yypact[yystate];
+ if (yypact_value_is_default (yyn))
+ goto yydefault;
+
+ /* Not known => get a lookahead token if don't already have one. */
+
+ /* YYCHAR is either empty, or end-of-input, or a valid lookahead. */
+ if (yychar == YYEMPTY)
+ {
+ YYDPRINTF ((stderr, "Reading a token\n"));
+ yychar = yylex <%= output.yylex_formals %>;
+ }
+
+ if (yychar <= <%= output.eof_symbol.id.s_value %>)
+ {
+ yychar = <%= output.eof_symbol.id.s_value %>;
+ yytoken = <%= output.eof_symbol.enum_name %>;
+ YYDPRINTF ((stderr, "Now at end of input.\n"));
+ }
+ else if (yychar == <%= output.error_symbol.id.s_value %>)
+ {
+ /* The scanner already issued an error message, process directly
+ to error recovery. But do not keep the error token as
+ lookahead, it is too special and may lead us to an endless
+ loop in error recovery. */
+ yychar = <%= output.undef_symbol.id.s_value %>;
+ yytoken = <%= output.error_symbol.enum_name %>;
+ yyerror_range[1] = yylloc;
+ goto yyerrlab1;
+ }
+ else
+ {
+ yytoken = YYTRANSLATE (yychar);
+ YY_SYMBOL_PRINT ("Next token is", yytoken, &yylval, &yylloc);
+ }
+
+ /* If the proper action on seeing token YYTOKEN is to reduce or to
+ detect an error, take that action. */
+ yyn += yytoken;
+ if (yyn < 0 || YYLAST < yyn || yycheck[yyn] != yytoken)
+ goto yydefault;
+ yyn = yytable[yyn];
+ if (yyn <= 0)
+ {
+ if (yytable_value_is_error (yyn))
+ goto yyerrlab;
+ yyn = -yyn;
+ goto yyreduce;
+ }
+
+ /* Count tokens shifted since error; after three, turn off error
+ status. */
+ if (yyerrstatus)
+ yyerrstatus--;
+
+ /* Shift the lookahead token. */
+ YY_SYMBOL_PRINT ("Shifting", yytoken, &yylval, &yylloc);
+ yystate = yyn;
+ YY_IGNORE_MAYBE_UNINITIALIZED_BEGIN
+ *++yyvsp = yylval;
+ YY_IGNORE_MAYBE_UNINITIALIZED_END
+ *++yylsp = yylloc;
+
+ /* Discard the shifted token. */
+ yychar = YYEMPTY;
+ goto yynewstate;
+
+
+/*-----------------------------------------------------------.
+| yydefault -- do the default action for the current state. |
+`-----------------------------------------------------------*/
+yydefault:
+ yyn = yydefact[yystate];
+ if (yyn == 0)
+ goto yyerrlab;
+ goto yyreduce;
+
+
+/*-----------------------------.
+| yyreduce -- do a reduction. |
+`-----------------------------*/
+yyreduce:
+ /* yyn is the number of a rule to reduce with. */
+ yylen = yyr2[yyn];
+
+ /* If YYLEN is nonzero, implement the default value of the action:
+ '$$ = $1'.
+
+ Otherwise, the following line sets YYVAL to garbage.
+ This behavior is undocumented and Bison
+ users should not rely upon it. Assigning to YYVAL
+ unconditionally makes the parser a bit smaller, and it avoids a
+ GCC warning that YYVAL may be used uninitialized. */
+ yyval = yyvsp[1-yylen];
+
+ /* Default location. */
+ YYLLOC_DEFAULT (yyloc, (yylsp - yylen), yylen);
+ yyerror_range[1] = yyloc;
+ YY_REDUCE_PRINT (yyn);
+ switch (yyn)
+ {
+<%= output.user_actions -%>
+
+ default: break;
+ }
+ /* User semantic actions sometimes alter yychar, and that requires
+ that yytoken be updated with the new translation. We take the
+ approach of translating immediately before every use of yytoken.
+ One alternative is translating here after every semantic action,
+ but that translation would be missed if the semantic action invokes
+ YYABORT, YYACCEPT, or YYERROR immediately after altering yychar or
+ if it invokes YYBACKUP. In the case of YYABORT or YYACCEPT, an
+ incorrect destructor might then be invoked immediately. In the
+ case of YYERROR or YYBACKUP, subsequent parser actions might lead
+ to an incorrect destructor call or verbose syntax error message
+ before the lookahead is translated. */
+ YY_SYMBOL_PRINT ("-> $$ =", YY_CAST (yysymbol_kind_t, yyr1[yyn]), &yyval, &yyloc);
+
+ YYPOPSTACK (yylen);
+ yylen = 0;
+
+ *++yyvsp = yyval;
+ *++yylsp = yyloc;
+
+ /* Now 'shift' the result of the reduction. Determine what state
+ that goes to, based on the state we popped back to and the rule
+ number reduced by. */
+ {
+ const int yylhs = yyr1[yyn] - YYNTOKENS;
+ const int yyi = yypgoto[yylhs] + *yyssp;
+ yystate = (0 <= yyi && yyi <= YYLAST && yycheck[yyi] == *yyssp
+ ? yytable[yyi]
+ : yydefgoto[yylhs]);
+ }
+
+ goto yynewstate;
+
+
+/*--------------------------------------.
+| yyerrlab -- here on detecting error. |
+`--------------------------------------*/
+yyerrlab:
+ /* Make sure we have latest lookahead translation. See comments at
+ user semantic actions for why this is necessary. */
+ yytoken = yychar == YYEMPTY ? YYSYMBOL_YYEMPTY : YYTRANSLATE (yychar);
+ /* If not already recovering from an error, report this error. */
+ if (!yyerrstatus)
+ {
+ ++yynerrs;
+ {
+ yypcontext_t yyctx
+ = {yyssp, yytoken, &yylloc};
+ char const *yymsgp = YY_("syntax error");
+ int yysyntax_error_status;
+ yysyntax_error_status = yysyntax_error (&yymsg_alloc, &yymsg, &yyctx);
+ if (yysyntax_error_status == 0)
+ yymsgp = yymsg;
+ else if (yysyntax_error_status == -1)
+ {
+ if (yymsg != yymsgbuf)
+ YYSTACK_FREE (yymsg);
+ yymsg = YY_CAST (char *,
+ YYSTACK_ALLOC (YY_CAST (YYSIZE_T, yymsg_alloc)));
+ if (yymsg)
+ {
+ yysyntax_error_status
+ = yysyntax_error (&yymsg_alloc, &yymsg, &yyctx);
+ yymsgp = yymsg;
+ }
+ else
+ {
+ yymsg = yymsgbuf;
+ yymsg_alloc = sizeof yymsgbuf;
+ yysyntax_error_status = YYENOMEM;
+ }
+ }
+ yyerror (<%= output.yyerror_args %>, yymsgp);
+ if (yysyntax_error_status == YYENOMEM)
+ YYNOMEM;
+ }
+ }
+
+ yyerror_range[1] = yylloc;
+ if (yyerrstatus == 3)
+ {
+ /* If just tried and failed to reuse lookahead token after an
+ error, discard it. */
+
+ if (yychar <= <%= output.eof_symbol.id.s_value %>)
+ {
+ /* Return failure if at end of input. */
+ if (yychar == <%= output.eof_symbol.id.s_value %>)
+ YYABORT;
+ }
+ else
+ {
+ yydestruct ("Error: discarding",
+ yytoken, &yylval, &yylloc<%= output.user_args %>);
+ yychar = YYEMPTY;
+ }
+ }
+
+ /* Else will try to reuse lookahead token after shifting the error
+ token. */
+ goto yyerrlab1;
+
+
+/*---------------------------------------------------.
+| yyerrorlab -- error raised explicitly by YYERROR. |
+`---------------------------------------------------*/
+yyerrorlab:
+ /* Pacify compilers when the user code never invokes YYERROR and the
+ label yyerrorlab therefore never appears in user code. */
+ if (0)
+ YYERROR;
+ ++yynerrs;
+
+ /* Do not reclaim the symbols of the rule whose action triggered
+ this YYERROR. */
+ YYPOPSTACK (yylen);
+ yylen = 0;
+ YY_STACK_PRINT (yyss, yyssp);
+ yystate = *yyssp;
+ goto yyerrlab1;
+
+
+/*-------------------------------------------------------------.
+| yyerrlab1 -- common code for both syntax error and YYERROR. |
+`-------------------------------------------------------------*/
+yyerrlab1:
+ yyerrstatus = 3; /* Each real token shifted decrements this. */
+
+ /* Pop stack until we find a state that shifts the error token. */
+ for (;;)
+ {
+ yyn = yypact[yystate];
+ if (!yypact_value_is_default (yyn))
+ {
+ yyn += YYSYMBOL_YYerror;
+ if (0 <= yyn && yyn <= YYLAST && yycheck[yyn] == YYSYMBOL_YYerror)
+ {
+ yyn = yytable[yyn];
+ if (0 < yyn)
+ break;
+ }
+ }
+
+ /* Pop the current state because it cannot handle the error token. */
+ if (yyssp == yyss)
+ YYABORT;
+
+ yyerror_range[1] = *yylsp;
+ yydestruct ("Error: popping",
+ YY_ACCESSING_SYMBOL (yystate), yyvsp, yylsp<%= output.user_args %>);
+ YYPOPSTACK (1);
+ yystate = *yyssp;
+ YY_STACK_PRINT (yyss, yyssp);
+ }
+
+ YY_IGNORE_MAYBE_UNINITIALIZED_BEGIN
+ *++yyvsp = yylval;
+ YY_IGNORE_MAYBE_UNINITIALIZED_END
+
+ yyerror_range[2] = yylloc;
+ ++yylsp;
+ YYLLOC_DEFAULT (*yylsp, yyerror_range, 2);
+
+ /* Shift the error token. */
+ YY_SYMBOL_PRINT ("Shifting", YY_ACCESSING_SYMBOL (yyn), yyvsp, yylsp);
+
+ yystate = yyn;
+ goto yynewstate;
+
+
+/*-------------------------------------.
+| yyacceptlab -- YYACCEPT comes here. |
+`-------------------------------------*/
+yyacceptlab:
+ yyresult = 0;
+ goto yyreturnlab;
+
+
+/*-----------------------------------.
+| yyabortlab -- YYABORT comes here. |
+`-----------------------------------*/
+yyabortlab:
+ yyresult = 1;
+ goto yyreturnlab;
+
+
+/*-----------------------------------------------------------.
+| yyexhaustedlab -- YYNOMEM (memory exhaustion) comes here. |
+`-----------------------------------------------------------*/
+yyexhaustedlab:
+ yyerror (<%= output.yyerror_args %>, YY_("memory exhausted"));
+ yyresult = 2;
+ goto yyreturnlab;
+
+
+/*----------------------------------------------------------.
+| yyreturnlab -- parsing is finished, clean up and return. |
+`----------------------------------------------------------*/
+yyreturnlab:
+ if (yychar != YYEMPTY)
+ {
+ /* Make sure we have latest lookahead translation. See comments at
+ user semantic actions for why this is necessary. */
+ yytoken = YYTRANSLATE (yychar);
+ yydestruct ("Cleanup: discarding lookahead",
+ yytoken, &yylval, &yylloc<%= output.user_args %>);
+ }
+ /* Do not reclaim the symbols of the rule whose action triggered
+ this YYABORT or YYACCEPT. */
+ YYPOPSTACK (yylen);
+ YY_STACK_PRINT (yyss, yyssp);
+ while (yyssp != yyss)
+ {
+ yydestruct ("Cleanup: popping",
+ YY_ACCESSING_SYMBOL (+*yyssp), yyvsp, yylsp<%= output.user_args %>);
+ YYPOPSTACK (1);
+ }
+#ifndef yyoverflow
+ if (yyss != yyssa)
+ YYSTACK_FREE (yyss);
+#endif
+ if (yymsg != yymsgbuf)
+ YYSTACK_FREE (yymsg);
+ return yyresult;
+}
+
+<%# b4_percent_code_get([[epilogue]]) -%>
+#line <%= output.aux.epilogue_first_lineno - 1 %> "<%= output.grammar_file_path %>"
+
+<%= output.aux.epilogue -%>
diff --git a/tool/lrama/template/bison/yacc.h b/tool/lrama/template/bison/yacc.h
new file mode 100644
index 0000000000..abcc46c1d6
--- /dev/null
+++ b/tool/lrama/template/bison/yacc.h
@@ -0,0 +1,112 @@
+<%# b4_generated_by -%>
+/* A Bison parser, made by GNU Bison 3.8.2. */
+
+<%# b4_copyright -%>
+/* Bison interface for Yacc-like parsers in C
+
+ Copyright (C) 1984, 1989-1990, 2000-2015, 2018-2021 Free Software Foundation,
+ Inc.
+
+ This program is free software: you can redistribute it and/or modify
+ it under the terms of the GNU General Public License as published by
+ the Free Software Foundation, either version 3 of the License, or
+ (at your option) any later version.
+
+ This program is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ GNU General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with this program. If not, see <https://www.gnu.org/licenses/>. */
+
+/* As a special exception, you may create a larger work that contains
+ part or all of the Bison parser skeleton and distribute that work
+ under terms of your choice, so long as that work isn't itself a
+ parser generator using the skeleton or a modified version thereof
+ as a parser skeleton. Alternatively, if you modify or redistribute
+ the parser skeleton itself, you may (at your option) remove this
+ special exception, which will cause the skeleton and the resulting
+ Bison output files to be licensed under the GNU General Public
+ License without this special exception.
+
+ This special exception was added by the Free Software Foundation in
+ version 2.2 of Bison. */
+
+<%# b4_disclaimer -%>
+/* DO NOT RELY ON FEATURES THAT ARE NOT DOCUMENTED in the manual,
+ especially those whose name start with YY_ or yy_. They are
+ private implementation details that can be changed or removed. */
+
+<%# b4_shared_declarations -%>
+<%# b4_shared_declarations -%>
+ <%-# b4_cpp_guard_open([b4_spec_mapped_header_file]) -%>
+ <%- if output.spec_mapped_header_file -%>
+#ifndef <%= output.b4_cpp_guard__b4_spec_mapped_header_file %>
+# define <%= output.b4_cpp_guard__b4_spec_mapped_header_file %>
+ <%- end -%>
+ <%-# b4_declare_yydebug & b4_YYDEBUG_define -%>
+/* Debug traces. */
+#ifndef YYDEBUG
+# define YYDEBUG 0
+#endif
+#if YYDEBUG
+extern int yydebug;
+#endif
+ <%-# b4_percent_code_get([[requires]]). %code is not supported -%>
+
+ <%-# b4_token_enums_defines -%>
+/* Token kinds. */
+#ifndef YYTOKENTYPE
+# define YYTOKENTYPE
+ enum yytokentype
+ {
+<%= output.token_enums -%>
+ };
+ typedef enum yytokentype yytoken_kind_t;
+#endif
+
+ <%-# b4_declare_yylstype -%>
+ <%-# b4_value_type_define -%>
+/* Value type. */
+#if ! defined YYSTYPE && ! defined YYSTYPE_IS_DECLARED
+union YYSTYPE
+{
+#line <%= output.grammar.union.lineno %> "<%= output.grammar_file_path %>"
+<%= output.grammar.union.braces_less_code %>
+#line [@oline@] [@ofile@]
+
+};
+typedef union YYSTYPE YYSTYPE;
+# define YYSTYPE_IS_TRIVIAL 1
+# define YYSTYPE_IS_DECLARED 1
+#endif
+
+ <%-# b4_location_type_define -%>
+/* Location type. */
+#if ! defined YYLTYPE && ! defined YYLTYPE_IS_DECLARED
+typedef struct YYLTYPE YYLTYPE;
+struct YYLTYPE
+{
+ int first_line;
+ int first_column;
+ int last_line;
+ int last_column;
+};
+# define YYLTYPE_IS_DECLARED 1
+# define YYLTYPE_IS_TRIVIAL 1
+#endif
+
+
+
+
+ <%-# b4_declare_yyerror_and_yylex. Not supported -%>
+ <%-# b4_declare_yyparse -%>
+int yyparse (<%= output.parse_param %>);
+
+
+ <%-# b4_percent_code_get([[provides]]). %code is not supported -%>
+ <%-# b4_cpp_guard_close([b4_spec_mapped_header_file]) -%>
+ <%- if output.spec_mapped_header_file -%>
+#endif /* !<%= output.b4_cpp_guard__b4_spec_mapped_header_file %> */
+ <%- end -%>
diff --git a/tool/make-snapshot b/tool/make-snapshot
index 841886a2db..3e5689e873 100755
--- a/tool/make-snapshot
+++ b/tool/make-snapshot
@@ -72,7 +72,7 @@ GITURL = URI.parse("https://github.com/ruby/ruby.git")
RUBY_VERSION_PATTERN = /^\#define\s+RUBY_VERSION\s+"([\d.]+)"/
ENV["VPATH"] ||= "include/ruby"
-YACC = ENV["YACC"] ||= "bison"
+YACC = ENV["YACC"] ||= "#{$tooldir}/lrama/exe/lrama"
ENV["BASERUBY"] ||= "ruby"
ENV["RUBY"] ||= "ruby"
ENV["MV"] ||= "mv"
diff --git a/win32/Makefile.sub b/win32/Makefile.sub
index 15e821cf43..1ff8a6fc20 100644
--- a/win32/Makefile.sub
+++ b/win32/Makefile.sub
@@ -101,7 +101,7 @@ CC = cl -nologo
CPP = $(CC) -E
!endif
!if !defined(YACC)
-YACC = bison
+YACC = $(BASERUBY) $(top_srcdir)/tool/lrama/exe/lrama
!endif
AR = lib -nologo
PURIFY =