mirror of
https://https.git.savannah.gnu.org/git/m4.git
synced 2026-01-27 01:44:29 +00:00
93726d6dd2
While a recursive descent parser is easy to write, it involves a LOT of function calls and boilerplate. Merely parsing "eval(1)" requires descending through ALL 11 levels of operator precedence, only for each layer to discover there is no operator. Better is the Pratt style of LR(1) parsing [1], which can handle any grammar where no two consecutive non-terminals or epsilon appear in the right side of any rule [2]. Now, parsing is done with just two mutually recursive functions; "eval(1)" works with just two function calls (primary() determines the value, and parse_expr() determines no operators are present), while more complicated expressions still produce the correct results but with less recursion. While at it, I noticed that "eval(1||(1/0))" used to produce a cryptic message: m4:stdin:1: bad expression in eval (excess input): 1||(1/0) despite the similar "eval(1||1/0)" suppressing that as part of short-circuiting. It turns out that my initial implementation of short-circuiting in 1.4.8b (back in 2007!) was never fully tested on more complex situations. To test that the new implementation is indeed faster, I wrote an m4 solution [3] to an Advent of Code challenge [4] that required computing 2000 iterations of a 24-bit linear feedback shift register over 2000 input values (--trace shows nearly 20 million eval calls). On my machine, runtime with an unoptimized pre-patch m4 was at 78 seconds, post-patch it completes in 66 seconds. [1] https://journal.stuffwithstuff.com/2011/03/19/pratt-parsers-expression-parsing-made-easy/ [2] https://en.wikipedia.org/wiki/Operator-precedence_parser [3] https://repo.or.cz/aoc_eblake.git/blob/1b122791d4:/2024/day22.m4 [4] https://adventofcode.com/2024/day/22 * NEWS: Document the bug fix. Also document recent compilation fixes. * cfg.mk (indent_args): Teach indent not to mangle int casts. * doc/m4.text (Eval): Add coverage for the bug fix. Adjust one error output that is now more precise. * src/eval.c (logical_or_term, logical_and_term, or_term, xor_term) (and_term, equality_term, cmp_term, shift_term, add_term, mult_term) (exp_term, unary_term, simple_term): Delete, replaced by... (primary, parse_expr): ...new functions. (evaluate): Adjust caller. (cherry picked from commit e3c4d07c56c0f85ef998067b59191c17c2188ab8)
57 lines
2.2 KiB
Makefile
57 lines
2.2 KiB
Makefile
# Customize maint.mk. -*- makefile -*-
|
|
# Copyright (C) 2003-2014, 2016-2017, 2020-2025 Free Software
|
|
# Foundation, Inc.
|
|
|
|
# This program is free software: you can redistribute it and/or modify
|
|
# it under the terms of the GNU General Public License as published by
|
|
# the Free Software Foundation, either version 3 of the License, or
|
|
# (at your option) any later version.
|
|
|
|
# This program is distributed in the hope that it will be useful,
|
|
# but WITHOUT ANY WARRANTY; without even the implied warranty of
|
|
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
|
# GNU General Public License for more details.
|
|
|
|
# You should have received a copy of the GNU General Public License
|
|
# along with this program. If not, see <https://www.gnu.org/licenses/>.
|
|
|
|
# Used in maint.mk's web-manual rule
|
|
manual_title = GNU macro processor
|
|
|
|
# Always use shorthand copyrights.
|
|
update-copyright-env = \
|
|
UPDATE_COPYRIGHT_USE_INTERVALS=1 \
|
|
UPDATE_COPYRIGHT_MAX_LINE_LENGTH=72
|
|
|
|
# Tests not to run as part of "make syntax-check".
|
|
local-checks-to-skip =
|
|
# M4 intentionally uses a coding style that compiles under C++.
|
|
local-checks-to-skip += sc_cast_of_x_alloc_return_value
|
|
|
|
# Our files include "m4.h", which in turn includes <config.h> first.
|
|
config_h_header = "m4\.h"
|
|
|
|
# Hash of NEWS contents, to ensure we don't add entries to wrong section.
|
|
old_NEWS_hash = 88ec470c5ac1bc9bd5a4ff3eab995c9b
|
|
|
|
# Update m4-latest.tar.* symlinks during 'make stable/beta'.
|
|
GNUPLOADFLAGS = --symlink-regex
|
|
|
|
# Indent only with spaces.
|
|
sc_prohibit_tab_based_indentation:
|
|
@re='^ * ' \
|
|
msg='TAB in indentation; use only spaces' \
|
|
$(_prohibit_regexp)
|
|
indent_args = --ignore-profile --preprocessor-indentation 1 --no-tabs \
|
|
-T int32_t -T uint32_t
|
|
|
|
# List all syntax-check exemptions:
|
|
exclude_file_name_regexp--sc_prohibit_tab_based_indentation = \
|
|
(^(GNU)?Makefile(\.am)?|\.mk|^HACKING|^ChangeLog.*)$$
|
|
exclude_file_name_regexp--sc_trailing_blank = ^examples/null
|
|
exclude_file_name_regexp--update-copyright = ^m4/gnulib-cache.m4$$
|
|
exclude_file_name_regexp--sc_codespell = ^THANKS$$
|
|
|
|
# Codespell exemptions:
|
|
codespell_ignore_words_list = ois,WIDTHn
|