LACTF 2026 - grammar

Write-up | lactf2026/misc/grammar

Description

Inspired by CS 131 Programming Languages, I decided to make a context-free grammar in EBNF for my flag! But it looks like some squirrels have eaten away at the parse tree…

Artifacts: tree.png

grammar-note.txt

---

Walkthrough

Firstly, I will summarize anything you actually need based on the given note and picture in the following bulletpoints:

• We have six colors of circle: black, yellow, blue, red, green, purple.
• Each colored circle represents a kind of “rules”. There are 5 rules: cd (stands for consonant and digit), vc (stands for vowel and consonant), vd (stands for vowel and digit), c (stands for consonant), and d (stands for digit). If a color has more than one appearance in the tree, any circle that has that color will follow the same rule.
• If a color only has one column of black circle, it means that color only represents one letter, and will follow one of these rules: c or d. Otherwise, if it has two columns, we know that color represents two letters, and follows either cd, vc or vd rule.

• We have a total of five consonants in order from c1 to c5: f, g, p, t, r; four digits in order from d1 to d4: 0, 1, 4, 5; three vowels in order from v1 to v3: e, o, u.
• Each black box in the bottom row represents a letter in our flag.
• We can skip the first 6 and the last letters, since we already know the format of the flag will be lactf{<flag>}. Moreover, in the middle of <flag>, there are some columns that starts from black circle and goes straight to the black box: those are the underscore symbol “_”.

Okay, now you know the context. Let’s begin.

I. Confirmed colors

Having a look at the tree and analysing, I confirm the rules of these two colors:

1. Blue: cd

Each has two columns, and one of these circles has the first column containing five black circles, so that column must follow the “c” rule (since “c” rule has 5 elements in total). In the rules we are provided, only “cd” satisfies my analysis.

1. Purple: vc

Each also has two columns, and there are two purple circles that has the second column containing five black circles, so the rule of that column must be “c” rule. Looking at all the rules, only “vc” is satisfied.

Now we are left with green, red and yellow. For now, I will skip these three and start building some pieces of the flag first.

II. Building flags

The flag format based on the tree is: lactf{_ _ _ _ _ _ _ _ _|_ _ _ _|_ _ _ _ _ _} NOTE: The underscores are needed to fill with letters and digits, and the “|” is for the underscores in the real flag.

With the information that I got in I, let’s get our first letters.

For instance, for blue (cd), we have two of ‘em:

The one on the left side is: c = 5, d = 1.

Checking the provided grammar, these two blanks have to be filled with: “r0”

I will just solve one circle as an example, for all of the next circles please follow the same rule.

By the way, after solving purple and blue circles, I got this:

lactf{_ r0 _ _ _ _ or|p4_ _|eg_er_ }

Let’s pay our attention to the last three colors: green, red and yellow. From now, I will rely on my guessing skill and intuition.

I will give yellow a try this time. This is a single-column color, so it is either “c” or “d”. Let’s try “c”.

For example, the left one has three black circles, and the right one has four, so they are “p” and “t”, respectively.

To speed up, I will fill the rest of yellow circles. You can double check it by referencing the grammar.

lactf{pr0f_ _ _ or|p4_ _|eggert}

It kinda makes sense to me. I can guess the first word is “professor”.

Next, we will try red circle. There’s only one red circle, right before the or in pr0 _ _ _ _ or. Since there is no “s” letter in “c” rule, red should follow “d” rule. This red has 4 black circles, and according to the grammar, it should be filled with “5” (see this if you do not know why).

lactf{pr0f_ _5or|p4_ _|eggert}

Lastly, we got green circles. Notice that we have 2 “s” in the word “professor”, and only “5” in the “d” rule can act as “s”, so the second column of green must follow “d” rule.

lactf{pr0f_55or|p4_1|eggert}

The last letter of “pr0f_55or” should be “e”. There’s “e” in the “v” rule, so the first column of green must follow this rule.

lactf{pr0fe55or|p4u1|eggert}

In conclusion, the flag that we need to find is lactf{pr0fe55or|p4u1|eggert}.