From a1b01e7701f9fc370f8dff777aad6d39a2c5a3e3 Mon Sep 17 00:00:00 2001 From: Yuichiro Kaneko Date: Fri, 12 May 2023 18:25:10 +0900 Subject: Use Lrama LALR parser generator instead of Bison https://bugs.ruby-lang.org/issues/19637 Co-authored-by: Nobuyoshi Nakada --- .github/workflows/baseruby.yml | 2 +- .github/workflows/bundled_gems.yml | 2 +- .github/workflows/check_dependencies.yml | 2 +- .github/workflows/codeql-analysis.yml | 2 +- .github/workflows/macos.yml | 3 +- .github/workflows/mingw.yml | 4 +- .github/workflows/rjit-bindgen.yml | 2 +- .github/workflows/rjit.yml | 2 +- .github/workflows/ubuntu.yml | 2 +- .github/workflows/wasm.yml | 2 +- .github/workflows/windows.yml | 1 - .github/workflows/yjit-ubuntu.yml | 2 +- common.mk | 7 +- defs/gmake.mk | 1 + doc/contributing/building_ruby.md | 1 - doc/windows.md | 7 +- ext/ripper/depend | 2 + ext/ripper/extconf.rb | 10 +- template/Makefile.in | 2 +- tool/lrama/exe/lrama | 7 + tool/lrama/lib/lrama.rb | 13 + tool/lrama/lib/lrama/bitmap.rb | 29 + tool/lrama/lib/lrama/command.rb | 144 +++ tool/lrama/lib/lrama/context.rb | 511 +++++++++ tool/lrama/lib/lrama/digraph.rb | 53 + tool/lrama/lib/lrama/grammar.rb | 850 +++++++++++++++ tool/lrama/lib/lrama/lexer.rb | 349 ++++++ tool/lrama/lib/lrama/output.rb | 370 +++++++ tool/lrama/lib/lrama/parser.rb | 321 ++++++ tool/lrama/lib/lrama/report.rb | 47 + tool/lrama/lib/lrama/states.rb | 832 ++++++++++++++ tool/lrama/lib/lrama/states_reporter.rb | 310 ++++++ tool/lrama/lib/lrama/version.rb | 3 + tool/lrama/lib/lrama/warning.rb | 25 + tool/lrama/template/bison/yacc.c | 1743 ++++++++++++++++++++++++++++++ tool/lrama/template/bison/yacc.h | 112 ++ tool/make-snapshot | 2 +- win32/Makefile.sub | 2 +- 38 files changed, 5749 insertions(+), 30 deletions(-) create mode 100755 tool/lrama/exe/lrama create mode 100644 tool/lrama/lib/lrama.rb create mode 100644 tool/lrama/lib/lrama/bitmap.rb create mode 100644 tool/lrama/lib/lrama/command.rb create mode 100644 tool/lrama/lib/lrama/context.rb create mode 100644 tool/lrama/lib/lrama/digraph.rb create mode 100644 tool/lrama/lib/lrama/grammar.rb create mode 100644 tool/lrama/lib/lrama/lexer.rb create mode 100644 tool/lrama/lib/lrama/output.rb create mode 100644 tool/lrama/lib/lrama/parser.rb create mode 100644 tool/lrama/lib/lrama/report.rb create mode 100644 tool/lrama/lib/lrama/states.rb create mode 100644 tool/lrama/lib/lrama/states_reporter.rb create mode 100644 tool/lrama/lib/lrama/version.rb create mode 100644 tool/lrama/lib/lrama/warning.rb create mode 100644 tool/lrama/template/bison/yacc.c create mode 100644 tool/lrama/template/bison/yacc.h 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: "$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) # + 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_]+>)?\$/) # $$, $$ + 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, $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 '\\' "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 . */ + +/* 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 (Val) +# define YY_REINTERPRET_CAST(Type, Val) reinterpret_cast (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 + and (if available) are included + so that the code can choose integer types of a good width. */ + +#ifndef __PTRDIFF_MAX__ +# include /* INFRINGES ON USER NAME SPACE */ +# if defined __STDC_VERSION__ && 199901 <= __STDC_VERSION__ +# include /* 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 + . */ +#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 /* 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 /* 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 /* 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 /* INFRINGES ON USER NAME SPACE */ +# elif defined _AIX +# define YYSTACK_ALLOC __alloca +# elif defined _MSC_VER +# include /* INFRINGES ON USER NAME SPACE */ +# define alloca _alloca +# else +# define YYSTACK_ALLOC alloca +# if ! defined _ALLOCA_H && ! defined EXIT_SUCCESS +# include /* 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 /* 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 /* 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 . */ + +/* 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 = -- cgit v1.2.3