1

I'm looking for a tool which automatically checks whether a LaTeX document is a correct bracket term.

It's very easy to write such a tool but before I do, I want to know whether one already exists.

It needs to be a command-line tool or shell code so I can use it in a script. A GUI tools just won't help me. It needs to check for the brackets () {} [] <>.

I view the document as a bracket expression. All the non-bracket characters don't matter. For a bracket term T with only 1 type of bracket to be valid, it needs to meet these conditions:

  • The number of opening and closing brackets in T must be equal.
  • There must be no prefix of T which contains more closing than opening brackets.

If there are several type of brackets (a set B of brackets), T must meet the above-mentioned conditions for all β ∈ B and all substrings of T induced by paired brackets must meet the above-mentioned conditions. A substring (t_1, ..., t_s) of T is said to be induced by paired brackets of type β iff (β_opening, t_1, ..., t_s, β_closing) is a substring of T.

  • Why are you only interested in bracket pairs? Why don't you just check that the compilation of your LaTeX file is successful? Would a LaTeX checker (see for example that question) suit your needs? – xhienne Sep 30 '17 at 23:00
  • That my code compiles, of course, is another pre-commit check. This one is about the document's contents. I might forget a bracket in a math formula or forget a closing parenthesis in normal English text. When my code doesn't compile, I definitely know about the problem soon. But when it's not a problem LaTeX cares about, I might never find out without a bracket expression validity checker. – UTF-8 Sep 30 '17 at 23:06
  • Something I've done many years ago, when taking CS classes but never bothered to upload anywhere: github.com/wvxvw/dyck-language-parser. You'd need to install GNU Bison and Flex to be able to compile this project. – wvxvw Oct 1 '17 at 9:55
3

With GNU grep built with PCRE support, you could do:

find . -size +0 -type f -exec \
  grep -zLP '\A((?:[^][<>{()}]++|<(?1)>|\{(?1)\}|\[(?1)\]|\((?1)\))*+)\z' {} +

To find such files (assuming they don't contain NUL bytes and that each is small enough to fit whole in memory).

Or call perl directly (allowing files with NUL bytes):

find . -size +0 -type f -exec perl -l -0777 -ne 'print $ARGV unless
  /^((?:[^][<>{()}]++|<(?1)>|\{(?1)\}|\[(?1)\]|\((?1)\))*)$/' {} +

Some perl/PCRE specific operators:

  • \A and \z match respectively at the start and end of the subject. Like ^ and $ (or with the -x option) but without ambiguity when the subject is multiline (needed in some versions of GNU grep).
  • ++ and *+ are the non-backtracking versions of the + and * operators. Here helps the regexp engine not to try too hard to find a match when we know it can't.
  • (?1) refers to the regexp in the corresponding capture group. That allows for recursive regexps.
  • (?:...), same as (...) but only for grouping (no capturing...)

Note that it finds a great proportions of the *.tex files on my system as </> are used for comparison operators in TeX and some of those characters are found unmatched in comments or escaped.

  • Sounds like requirements virtually all LaTeX files meet. I ran the same tests as for the other answer and it looks like this works, too. Is -P needed? The man page says it's experimental. – UTF-8 Oct 1 '17 at 10:15
  • -P is for PCRE needed for many of the operators there. It's been experimental for decades, and it's true it has a few quirks. I'll add the perl equivalent for something not advertised as experimental. – Stéphane Chazelas Oct 1 '17 at 10:20
  • When I use tr < <FILENAME> -d '\000' | grep -zLP '\A((?:[^][<>{()}]++|<(?1)>|\{(?1)\}|\[(?1)\]|\((?1)\))*+)\z', it works even if the file contains null characters, right? – UTF-8 Oct 1 '17 at 10:35
  • @UTF-8, yes, though a file with a NUL byte is not a text file, so I wouldn't worry two much (your LaTeX interpreter would likely choke on those, you'd also have issues with incorrectly encoded files). See the perl variant that doesn't have the limitation. It's not so much that it doesn't work at all but that grep would try to match the regexp again each of the NUL delimited records. – Stéphane Chazelas Oct 1 '17 at 10:45
  • Thank you. Then I think your answer is better. My LaTeX compiler actually does choke on a null character. Emacs and Atom still display the tex file correctly but GEdit suddenly think the file's contents are in Chinese for some reason. It only displays Chinese characters, even though it's all English plus a null character. ^^ I'll accept your answer instead of the other one and upvote both. – UTF-8 Oct 1 '17 at 12:28
3

I don't know of any program that would only check for the proper pairing of brackets without annoying you with other unrelated syntax errors, depending on the language those checkers are targeted to.

Since, as you said, it is easy to write such a tool, here is a small script that hopefully will do the job:

#!/bin/sh

# If a file is given as 1st parameter, use it, else use stdin
[ "$#" -gt 0 ] && exec < "$1"

# A correct input file should result in an empty string
tr -d -c '{}[]()<>' |
sed '
    # Eliminate adjacent bracket pairs one by one
    :loop
    s/\[\]\|()\|{}\|<>//g
    t loop
' |
if grep -q .; then
    echo "ERROR: unpaired brackets!"
else
    echo "OK: all brackets are paired."
fi

If your sed implementation doesn't support the (non-standard) \| alternation operator, you can replace that s command with 4:

s/\[\]//g
s/{}//g
s/()//g
s/<>//g

The tr command above is standard, but some (SysV based ones) will complain about such an unescaped [ not containing a range. With those, you can escape the [ with \ (tr -cd '{}()<>\[]') but then it becomes unspecified per POSIX and some would fail to delete the backspace character. For portability, on ASCII-based systems, you can can use tr -cd '{}()<>\133\135'.

  • Thank you! I checked it against the document I discovered a missing closing bracket yesterday and it didn't check out. I fixed the mistake and it did check out. It also worked for a few test one-liners I tried, except for the empty string / strings without brackets. This is easy to circumvent, though. I would've written a small C program containing a stack-based algorithm if no one answered after a few days but a bash script is of course suited much better for a git hook. So thank you very much! – UTF-8 Sep 30 '17 at 23:52
  • 1
    @UTF-8 You probably mean that the sed program does not display anything when the input does not contain any bracket. I fixed this by putting the test outside sed. – xhienne Oct 1 '17 at 0:02
  • Yes, exactly. Thank you. I think the way it's now is way more elegant. – UTF-8 Oct 1 '17 at 0:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.