What is AST?

  • AST is the acronym of Abstract Syntax Tree
  • An abstract syntax tree is essentially a JS object that parses Html tags into JS objects from a string perspective
  • The render function (h function), which is both a product of AST and the origin of VNodes
h('div', { attrs: { className: 'box' } }, [
    h('ul', {}, [
        h('li', {}, '1'),
        h('li', {}, '2'),
        h('li', {}, '3')]])Copy the code

Abstract syntax tree and virtual node relationship

Working mechanism

<div>
  <h3 class="box" title="Title" data-type="3">hello</h3>
  <ul>
    <li>A</li>
    <li>B</li>
    <li>C</li>
  </ul>
</div>
Copy the code

Convert to the following AST tree

{
    tag: "div".attrs: [].children: [{tag: "h3".attrs: [{name: "name".value: "box" },
                { name: "title".value: "Title" },
                { name: "data-type".value: "3"}].children: [{text: "Hello".type: "3"}]}, {tag: "ul".attrs: [].children: [{tag: 'li'.children: [{ text: "A".type: "3"}].attrs: []}, {tag: 'li'.children: [{ text: "B".type: "3"}].attrs: []}, {tag: 'li'.children: [{ text: "C".type: "3"}].attrs: []}]}}Copy the code

The necessary algorithm store

recursive

  • Scenario technique used: Rule repetition
  • Recursion case one
Fibonacci sequence, sum the first N terms1 1 2 3 5 8 13 21 34 55
Copy the code
  • Recursion case two
Add a higher dimensional array [1.2[3[4.5].6].7[8].9] convert to this object (the teacher made a mistake during the explanation process, the following is the picture from the beginning of PPT) {children: [{value: 1 },
        { value: 2 },
        {
            children: [{value: 3 },
                {
                    children: [{value: 4 },
                        { value: 5}]}, {value: 6}]}, {value: 7 },
        {
            children: [{value: 8}]}, {value: 9}}]Copy the code

The stack

  • Scenario techniques used: lexical analysis, template strings
  • case
// smartRepeat smartRepeat string problem
将 '3[abc]'into'abcabcabc'
将 '3[2[a]2[b]]'become'aabbaabbaabb'
将 '2[1[a]3[b]2[3[c]4[d]]]'become'abbbcccddddcccddddabbbcccddddcccdddd'
Copy the code

Iterate over each character

  • Create two stacks
  • If the character is a number, the number is pushed 1 and the empty string is pushed 2
  • If the character is a letter, change the top entry of stack 2 to this letter at this point
  • If this character is], then we will change the number fromStack 1Pop the stack, just put itStack 2Duplicate elements at the top of the stackStack 1The number of times the number pops up,Stack 2Pop stack, splice toStack 2The new stack top

The project structure

|-- study-ast |-- .gitignore |-- package-lock.json |-- package.json |-- readme.md |-- webpack.config.js |-- page | |-- Index.html | - SRC | -- index. | js / / entry -- parse. Js / / main functions: The template string is converted to the AST tree structure | -- parseAttribute. Js / / parsing HTML tag attributes in the attribute reserve case | | - examples / / algorithm -- max_count. Js / / continuous character repeat the most times | -- recursion_one. Js / / recursive case 1: the Fibonacci sequence | -- recursion_two. Js / / recursive case 2 | -- stack. Js / / stack smartRepeat intelligent repeated string problemCopy the code

Code Address:

Github.com/AFine970/st…

conclusion

  • I’m writing the pivot functionparse.jsWhen, the use of the algorithm is the stack, using the idea of the stack algorithm reserve
  • The stack mentality is useful when parsing template strings, allowing for quick parsing of nested HTML

The resources

b23.tv/B1bsTt